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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1395-count-number-of-teams-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。