C++ Tìm số cặp duy nhất trong mảng

Bài toán yêu cầu đếm tất cả các cặp duy nhất có thể tạo thành từ mảng đã cho, tức là mọi cặp có thể hình thành mà mỗi cặp phải duy nhất. Ví dụ:

Input: array[] = { 5, 5, 9 } → Output: 4
Giải thích: Các cặp duy nhất: (5,5), (5,9), (9,5), (9,9)

Input: array[] = { 5, 4, 3, 2, 2 } → Output: 16

Các phương pháp giải

Phương pháp vét cạn (Brute Force)

Duyệt qua mọi cặp có thể, thêm vào tập hợp (set) để loại trùng lặp, cuối cùng lấy kích thước tập hợp. Độ phức tạp: O(n² log n).

Ví dụ

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

int main() {
    int arr[] = { 5, 4, 3, 2, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    set<pair<int, int>> set_of_pairs;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            set_of_pairs.insert(make_pair(arr[i], arr[j]));

    int result = set_of_pairs.size();
    cout << "Số cặp duy nhất: " << result;
    return 0;
}

Kết quả

Số cặp duy nhất: 16

Phương pháp hiệu quả

Tìm số phần tử duy nhất trong mảng (gọi là k). Mỗi phần tử duy nhất có thể tạo cặp với mọi phần tử duy nhất (kể cả chính nó), do đó số cặp duy nhất = k². Độ phức tạp: O(n).

Ví dụ

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

int main() {
    int arr[] = { 5, 4, 3, 2, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    unordered_set<int> set_of_elements;

    for (int i = 0; i < n; i++)
        set_of_elements.insert(arr[i]);

    int size = set_of_elements.size();
    int result = size * size;
    cout << "Số cặp duy nhất trong mảng: " << result;
    return 0;
}

Kết quả

Số cặp duy nhất trong mảng: 16

Kết luận

Bài viết trình bày hai cách giải: vét cạn O(n² log n) và hiệu quả O(n) bằng cách đếm phần tử duy nhất rồi bình phương. Có thể triển khai bằng C, Java, Python, v.v. Hy vọng hữu ích.