题目大意：
统计作战单位数
n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。
每 3 个士兵可以组成一个作战单位，分组规则如下：
- 从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
- 作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中 0 <= i < j < k < n
请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。
示例 1：
输入：rating = [2,5,3,4,1] 输出：3 解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。
示例 2：
输入：rating = [2,1,3] 输出：0 解释：根据题目条件，我们无法组建作战单位。
示例 3：
输入：rating = [1,2,3,4] 输出：4
提示：
n == rating.length1 <= n <= 2001 <= rating[i] <= 10^5
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1395
解题思路分析：
解法一：
周赛时看到本题的数据规模不大，因此第一时间就意识到本题使用n三次方是可行的。也就是说我们可以使用三层循环，暴力遍历每一种组合情况，如果当前组合的三个人满足题目条件，返回结果加一即可。
实现代码：
public int numTeams(int[] rating) {
int res=0;
for(int i=0;i<rating.length;i++){
for(int j=i+1;j<rating.length;j++){
for(int k=j+1;k<rating.length;k++){
if(rating[j]>rating[i]&&rating[k]>rating[j]) res++;
if(rating[j]<rating[i]&&rating[k]<rating[j]) res++;
}
}
}
return res;
} 本题解法执行时间为16ms。
Runtime: 16 ms, faster than 66.17% of Java online submissions for Count Number of Teams.
Memory Usage: 37.1 MB, less than 100.00% of Java online submissions for Count Number of Teams.
解法二：
其实本题可以降维至n平方来解决。我们假设当前数字是三个数字中的中间数。然后对于每个中间数，我们求出他左边所有大于他的个数leftbigger，以及小于它的个数leftSmaller。另外再求出该中间数右边大于他的个数rightbigger，以及小于它的个数rightSmaller。因此对于该中间数能够组成的合理解个数为：leftbigger*rightSmaller+leftSmaller*rightbigger.
实现代码：
public int numTeams(int[] rating) {
int res=0;
for(int i=1;i<rating.length-1;i++){
int leftbigger=0;
int leftSmaller=0;
for(int j=0;j<i;j++){
if(rating[j]>rating[i])leftbigger++;
if(rating[j]<rating[i])leftSmaller++;
}
int rightbigger=0;
int rightSmaller=0;
for(int j=i+1;j<rating.length;j++){
if(rating[j]>rating[i])rightbigger++;
if(rating[j]<rating[i])rightSmaller++;
}
res+= leftbigger*rightSmaller+leftSmaller*rightbigger;
}
return res;
} 本题解法执行时间为2ms。
Runtime: 2 ms, faster than 99.71% of Java online submissions for Count Number of Teams.
Memory Usage: 37.1 MB, less than 100.00% of Java online submissions for Count Number of Teams.
Kotlin版本：
fun numTeams(rating: IntArray): Int {
var res :Int = 0;
for(i in 1..(rating.lastIndex-1)){
var leftBigger=0;
var leftSmaller=0;
for(j in 0..i-1){
if(rating[j]<rating[i]) leftSmaller++;
else if(rating[j]>rating[i]) leftBigger++;
}
var rightBigger=0;
var rightSmaller=0;
for(j in i+1..rating.lastIndex){
if(rating[j]<rating[i]) rightSmaller++;
else if(rating[j]>rating[i]) rightBigger++;
}
res+=leftBigger*rightSmaller+leftSmaller*rightBigger;
}
return res;
} Runtime: 176 ms, faster than 90.91% of Kotlin online submissions for Count Number of Teams.
Memory Usage: 34.7 MB, less than 100.00% of Kotlin online submissions for Count Number of Teams.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1395-count-number-of-teams-解题思路分析/