Đếm cặp chỉ số có giá trị bằng nhau trong mảng (ghép găng tay) C++

Cho mảng N phần tử (kích cỡ găng tay > 0). Đếm số cặp chỉ số (i,j) với i 0. Mỗi phần tử chỉ dùng trong 1 cặp (sau khi ghép đổi thành -1).

Ví dụ minh họa

Ví dụ 1:

• Input: Arr = {4, 3, 2, 1, 2, 4}, N = 6
• Output: 2
• Giải thích: Cặp (4,4) tại (0,5) → đổi thành -1. Cặp (2,2) tại (2,4) → đổi thành -1. Kết quả 2 cặp.

Ví dụ 2:

• Input: Arr = {2, 2, 2, 2, 2}, N = 5
• Output: 2
• Giải thích: (0,1) và (2,3) → 2 cặp. Phần tử index 4 thừa.

Mã nguồn C++

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

int countPairs(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] == arr[j] && arr[i] > 0 && arr[j] > 0) {
                count++;
                arr[i] = arr[j] = -1; // Đánh dấu đã dùng
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {1, 2, 4, 2, 1, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Cap gang tay (cap phan tu bang nhau): " << countPairs(arr, n);
    return 0;
}

Kết quả chạy chương trình

Cap gang tay (cap phan tu bang nhau): 3

Phân tích logic

Thuật toán tham lam: duyệt i từ trái sang, với mỗi i tìm j đầu tiên > i có cùng giá trị. Điều này cho kết quả đúng vì:

• Mỗi phần tử chỉ dùng 1 lần.
• Thứ tự ưu tiên cặp có chỉ số nhỏ trước không ảnh hưởng tổng số cặp tối đa (với điều kiện giá trị > 0).

Tối ưu hóa O(n) - Đếm tần suất

Vì mỗi giá trị v xuất hiện freq[v] lần, số cặp tối đa từ giá trị đó là freq[v] / 2 (chia nguyên).

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

int countPairsOptimized(int arr[], int n) {
    unordered_map freq;
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) freq[arr[i]]++;
    }
    int count = 0;
    for (auto& [val, f] : freq) {
        count += f / 2;
    }
    return count;
}

Độ phức tạp

Lưu ý

• Phiên bản O(n) không thay đổi mảng gốc.
• Điều kiện arr[i] > 0 loại bỏ giá trị -1 (đã dùng) và giá trị ≤ 0 trong input.