统计作战单位数

LeetCode第1395题

题目描述：
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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-number-of-teams

思路：
最开始做这道题时，想着将其排序，然后用一个数组记录其原来的下标，依据三个下标是否为升序或者逆序，来判断其能否组成一个作战单位。但是这种办法感觉本质上并没有使问题更清晰。因为问题的本质在于数组的下标和数组的值都要为顺序或者一个顺序一个逆序。排序的手段只是交换了数组的值和下标的“位置”（排序后的值按升序排列，可看做是数组下标，而原来的下标被打乱了）。所以就放弃这种思路了。
于是想到用暴力法来做，设定i,j,k三个变量，分别遍历，时间复杂度为立方级别。
后来又看了评论，知道可以用固定中间位置的方式来做，统计左边比中间位置值小的个数cntl1，和右边比中间位置值大的个数cntr1（升序），或者统计左边比中间位置值大的个数cntl2，和右边比中间位置值大的个数cntr2（降序）。最后左右两边的个数相乘，就是结果。

源代码：

int numTeams(int* rating, int ratingSize){
//暴力算法，三个for循环
    int i,j,k;
    int cnt = 0;
    for(i = 0;i < ratingSize - 2;i++){
        for(j = i + 1;j < ratingSize - 1;j++){
        if(rating[i] < rating[j]){
            for(k = j + 1;k < ratingSize;k++){
                if(rating[j] < rating[k])
                    ++cnt;
            }
        }
        else{
            for(k = j + 1;k < ratingSize;k++){
                if(rating[j] > rating[k])
                    ++cnt;
            }
        }
    }
    }

    return cnt;
}

int numTeams(int* rating, int ratingSize){
//取中间固定值方法
    int mid,left,right;
    int cntl1,cntr1,cntl2,cntr2;
    int cnt = 0;

    for(mid = 0;mid < ratingSize;mid++){
        cntl1 = cntl2 = cntr1 = cntr2 = 0;
        for(left = 0;left < mid;left++){
            if(rating[left] < rating[mid]){
                ++cntl1;
            }
            else{
                ++cntl2;
            }
        }

        for(right = mid + 1;right < ratingSize;right++){
            if(rating[right] > rating[mid]){
                ++cntr1;
            }
            else{
                ++cntr2;
            }
        }

        cnt += (cntl1 * cntr1 + cntl2 * cntr2);
    }
        return cnt;
}

分析

暴力方法采用嵌套的三个for循环，时间复杂度为立方级别
取中间固定值方法，对于每一个固定值，都要循环遍历其左右共n - 1个数，一共需遍历n个中间值，所以时间复杂度为平方级别。