There are n
soldiers standing in a line. Each soldier is assigned a unique rating
value.
You have to form a team of 3 soldiers amongst them under the following rules:
- Choose 3 soldiers with index (
i
,j
,k
) with rating (rating[i]
,rating[j]
,rating[k]
). - A team is valid if: (
rating[i] < rating[j] < rating[k]
) or (rating[i] > rating[j] > rating[k]
) where (0 <= i < j < k < n
).
Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).
Example 1:
Input: rating = [2,5,3,4,1] Output: 3 Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).
Example 2:
Input: rating = [2,1,3] Output: 0 Explanation: We can't form any team given the conditions.
Example 3:
Input: rating = [1,2,3,4] Output: 4
Constraints:
n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5
Solution 1: Brute Force
Time complexity: O(n^3)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int numTeams(vector<int>& rating) { int n = rating.size(); int ans = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) for (int k = j + 1; k < n; ++k) if (rating[i] < rating[j] && rating[j] < rating[k] || rating[i] > rating[j] && rating[j] > rating[k]) ++ans; return ans; } }; |
Solution 2: Math
For each soldier j, count how many soldiers on his left has smaller ratings as left[j], count how many soldiers his right side has larger ratings as right[j]
ans = sum(left[j] * right[j] + (j – left[j]) * (n – j – 1 * right[j])
Time complexity: O(n^2)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 4 ms class Solution { public: int numTeams(vector<int>& rating) { int n = rating.size(); int ans = 0; for (int j = 0; j < n; ++j) { int l = 0; int r = 0; for (int i = 0; i < j; ++i) if (rating[i] < rating[j]) ++l; for (int k = j + 1; k < n; ++k) if (rating[j] < rating[k]) ++r; ans += (l * r) + (j - l) * (n - j - 1 - r); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment