LeetCode第1395題
題目描述：
n 名士兵站成一排原押。每個(gè)士兵都有一個(gè) 獨(dú)一無(wú)二 的評(píng)分 rating 搂赋。
每 3 個(gè)士兵可以組成一個(gè)作戰(zhàn)單位，分組規(guī)則如下：
從隊(duì)伍中選出下標(biāo)分別為 i炒嘲、j轴或、k 的 3 名士兵，他們的評(píng)分分別為 rating[i]、rating[j]灵迫、rating[k]
作戰(zhàn)單位需滿足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] 喧笔，其中 0 <= i < j < k < n
請(qǐng)你返回按上述條件可以組建的作戰(zhàn)單位數(shù)量。每個(gè)士兵都可以是多個(gè)作戰(zhàn)單位的一部分龟再。
示例 1：
輸入：rating = [2,5,3,4,1]
輸出：3
解釋：我們可以組建三個(gè)作戰(zhàn)單位 (2,3,4)书闸、(5,4,1)、(5,3,1) 利凑。
示例 2：
輸入：rating = [2,1,3]
輸出：0
解釋：根據(jù)題目條件浆劲，我們無(wú)法組建作戰(zhàn)單位。
示例 3：
輸入：rating = [1,2,3,4]
輸出：4
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-number-of-teams
思路：
最開(kāi)始做這道題時(shí)哀澈，想著將其排序牌借，然后用一個(gè)數(shù)組記錄其原來(lái)的下標(biāo)，依據(jù)三個(gè)下標(biāo)是否為升序或者逆序割按，來(lái)判斷其能否組成一個(gè)作戰(zhàn)單位膨报。但是這種辦法感覺(jué)本質(zhì)上并沒(méi)有使問(wèn)題更清晰。因?yàn)閱?wèn)題的本質(zhì)在于數(shù)組的下標(biāo)和數(shù)組的值都要為順序或者一個(gè)順序一個(gè)逆序适荣。排序的手段只是交換了數(shù)組的值和下標(biāo)的“位置”（排序后的值按升序排列现柠，可看做是數(shù)組下標(biāo)，而原來(lái)的下標(biāo)被打亂了）弛矛。所以就放棄這種思路了够吩。
于是想到用暴力法來(lái)做，設(shè)定i,j,k三個(gè)變量丈氓，分別遍歷周循，時(shí)間復(fù)雜度為立方級(jí)別。
后來(lái)又看了評(píng)論万俗，知道可以用固定中間位置的方式來(lái)做湾笛，統(tǒng)計(jì)左邊比中間位置值小的個(gè)數(shù)cntl1，和右邊比中間位置值大的個(gè)數(shù)cntr1（升序）闰歪，或者統(tǒng)計(jì)左邊比中間位置值大的個(gè)數(shù)cntl2嚎研，和右邊比中間位置值大的個(gè)數(shù)cntr2（降序）。最后左右兩邊的個(gè)數(shù)相乘课竣，就是結(jié)果嘉赎。
源代碼：
int numTeams(int* rating, int ratingSize){
//暴力算法，三個(gè)for循環(huán)
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;
}
分析
暴力方法采用嵌套的三個(gè)for循環(huán)于樟，時(shí)間復(fù)雜度為立方級(jí)別
取中間固定值方法公条，對(duì)于每一個(gè)固定值，都要循環(huán)遍歷其左右共n - 1個(gè)數(shù)迂曲，一共需遍歷n個(gè)中間值靶橱，所以時(shí)間復(fù)雜度為平方級(jí)別。
