LEETCODE 1395. Count Number of Teams 解题思路分析

题目大意：

统计作战单位数

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.length
• 1 <= n <= 200
• 1 <= 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.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1395-count-number-of-teams-解题思路分析/