Đếm số lượng đội trong C++

Giới thiệu

Cho n chiến binh xếp hàng, mỗi người có rating duy nhất. Cần đếm số đội 3 người (i, j, k) với i < j < k thỏa mãn:

• rating[i] < rating[j] < rating[k] (tăng dần) HOẶC
• rating[i] > rating[j] > rating[k] (giảm dần).

Mỗi chiến binh có thể thuộc nhiều đội khác nhau.

Giải pháp vét cạn (Brute Force)

Duyệt tất cả triplet (i, j, k) với 3 vòng lặp lồng nhau. Độ phức tạp O(n³), chấp nhận được với n ≤ 200.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numTeams(vector<int>& v) {
        int ret = 0, 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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2, 5, 3, 4, 1};
    cout << ob.numTeams(v); // Output: 3
    return 0;
}

Tối ưu hóa (O(n²))

Với mỗi j làm trung tâm, đếm số có rating nhỏ hơn và lớn hơn v[j], tương tự cho k > j. Số đội hợp lệ = (số nhỏ hơn bên trái * số lớn hơn bên phải) + (số lớn hơn bên trái * số nhỏ hơn bên phải).

Độ phức tạp

• Brute force: O(n³) thời gian, O(1) không gian.
• Tối ưu: O(n²) thời gian, O(1) không gian.