题目:
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
请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。
示例:
输入:rating = [2,5,3,4,1]
输出:3
解释:我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。
解题方法:
遍历[1,n-1]的士兵,对于第i个士兵,我们把他当做要选择作战单位的中间士兵,然后只需要统计在这个士兵左边/右边,大于/小于该士兵i评分rating。下面详细说明一下为什么这么做:
- 首先统计第i个士兵大于左边士兵rating的数量,记做lb;再记录小于右边的数量rs;现在满足条件的排列数为lb*rs(组合)
- 然后统计第i个士兵小于左边士兵rating的数量,记做ls;再记录大于右边的数量rb;现在满足条件的排列数为ls*rb(组合)
- 遍历完[1,n-1]的士兵,将所有统计的可能组合累加,得到最终结果。
为什么这样统计出来的没有重复呢?仔细想想,关键在于选择中间人作为筛选的条件,当筛选第i个士兵的时候,所有的组合都是i为中间人,但是当筛选第i+k个人的时候,i不可能在中间,所以这种遍历方式保证了不会出现重复的排列。
代码和结果:
class Solution {
public:
int numTeams(vector<int>& rating) {
int nums=rating.size();
int cnt=0;
for(int i=1;i<nums-1;i++)
{
int lb=0;
int ls=0;
int rb=0;
int rs=0;
for(int j=0;j<i;j++)
{
if(rating[j]>rating[i])
lb++;
else if(rating[j]<rating[i])
ls++;
}
for(int j=i+1;j<nums;j++)
{
if(rating[j]>rating[i])
rs++;
else if(rating[j]<rating[i])
rb++;
}
cnt+=lb*rb+ls*rs;
}
return cnt;
}
};
运行结果:第200道题了,加油!
原题链接:https://leetcode-cn.com/problems/count-number-of-teams/