1. 題目

n 名士兵站成一排。每個(gè)士兵都有一個(gè) 獨(dú)一無二 的評(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ù)題目條件，我們無法組建作戰(zhàn)單位。示例 3： 輸入：rating = [1,2,3,4] 輸出：4提示： n == rating.length 1 <= n <= 200 1 <= rating[i] <= 10^5

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-number-of-teams
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

2.1 蠻力解

• 數(shù)據(jù)量小，直接3層循環(huán)，$O(n^3)$ 時(shí)間復(fù)雜度

class Solution { public:int numTeams(vector<int>& rating) {int i, j, k, sum = 0, n = rating.size();for(i = 0; i < n-2; ++i)for(j = i+1; j < n-1; ++j)for(k = j+1; k < n; ++k)if((rating[i] < rating[j] && rating[j] < rating[k])||(rating[i] > rating[j] && rating[j] > rating[k]))sum++;return sum;} };

140 ms 7.6 MB

2.2 優(yōu)化蠻力

• 找到每個(gè)位置的左右比其大和小的個(gè)數(shù)，$O(n^2)$ 時(shí)間復(fù)雜度
• sum += lsmall*rLarge + lLarge*rsmall

class Solution { public:int numTeams(vector<int>& rating) {int i, j, lsmall, lLarge, rsmall, rLarge, sum = 0, n = rating.size();for(i = 1; i < n-1; ++i){lsmall = lLarge = rsmall = rLarge = 0;for(j = 0; j < i; ++j){if(rating[j] < rating[i])lsmall++;if(rating[j] > rating[i])lLarge++;}for(j = i+1; j < n; ++j){if(rating[j] < rating[i])rsmall++;if(rating[j] > rating[i])rLarge++;}sum += lsmall*rLarge + lLarge*rsmall;}return sum;} };

8 ms 7.3 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1395. 统计作战单位数（蛮力法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。