สมมติว่ามีทหาร n คนยืนเข้าแถว ที่นี่ทหารแต่ละคนจะได้รับค่าการจัดอันดับที่ไม่ซ้ำกัน เราต้องสร้างทีมทหาร 3 นายโดยใช้กฎต่อไปนี้ -
เลือกทหาร 3 นายที่มีดัชนี (i, j, k) ที่เรตติ้ง (เรตติ้ง[i], เรต[j], เรตติ้ง[k])
ทีมจะมีผลถ้า − (คะแนน[i] <เรตติ้ง[j] <เรตติ้ง[k]) หรือ (เรตติ้ง[i]> เรต[j]> เรต[k])
เราต้องหาจำนวนทีมที่เราสามารถสร้างได้ (ทหารสามารถเป็นส่วนหนึ่งของทีมได้หลายทีม)
ดังนั้นหากอินพุตเป็นเหมือนเรตติ้ง =[2,5,3,4,1] ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถสร้างสามทีมเช่น (2,3,4), (5,4,1) , (5,3,1).
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=0, n :=ขนาดของ v
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
สำหรับการเริ่มต้น j :=i + 1 เมื่อ j
-
สำหรับการเริ่มต้น k :=j + 1 เมื่อ k
-
ถ้า v[i]
-
(เพิ่มการถอยกลับโดย 1)
-
-
มิฉะนั้นเมื่อ v[i]> v[j] และ v[j]> v[k] แล้ว −
-
(เพิ่มการถอยกลับโดย 1)
-
-
-
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numTeams(vector<int>& v) {
int ret = 0;
int n = v.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (v[i] < v[j] && v[j] < v[k])
ret++;
else if (v[i] > v[j] && v[j] > v[k])
ret++;
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {2,5,3,4,1};
cout << (ob.numTeams(v));
} อินพุต
{2,5,3,4,1} ผลลัพธ์
3
