Đếm cặp duy nhất (arr[i], arr[j]) với i < j trong C++

Cho mảng số nguyên. Đếm số cặp duy nhất (arr[i], arr[j]) với chỉ số i < j.

Ví dụ

Đầu vào − arr[] = {1,2,3}

Đầu ra − 3

Giải thích − (1,2), (1,3), (2,3).

Đầu vào − arr[] = {4,4,3,2}

Đầu ra − 4

Giải thích − (4,4), (4,3), (4,2), (3,2).

Phương pháp giải

Cách 1 (naive): Duyệt 2 vòng lặp i=0..n-2, j=i+1..n-1, thêm cặp vào set>. Kết quả = size của set.

Cách 2 (hiệu quả): Tính số phần tử duy nhất phía sau mỗi chỉ số. Duyệt từ cuối, dùng set check lưu phần tử đã thấy. arr_2[i] = số phần tử duy nhất sau i. Sau đó duyệt từ đầu, dùng set uncheck bỏ qua phần tử trùng, cộng arr_2[i] vào count.

• Cách 1: set> se, lặp 2 vòng, se.insert({arr[i],arr[j]}).
• Cách 2: mảng arr_2, 2 set check, uncheck, duyệt ngược và xuôi.

Ví dụ code (naive)

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

int unique_pair(int arr[], int size) {
    int count = 0;
    set<pair<int, int>> se;
    for (int i = 0; i < size - 1; i++)
        for (int j = i + 1; j < size; j++)
            se.insert({arr[i], arr[j]});
    count = se.size();
    return count;
}

int main() {
    int arr[] = {4, 3, 1, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of unique pairs (arr[i], arr[j]) such that i < j are: " << unique_pair(arr, size);
    return 0;
}

Đầu ra

Count of unique pairs (arr[i], arr[j]) such that i < j are: 10

Ví dụ code (hiệu quả)

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

int unique_pair(int arr[], int size) {
    int count = 0, temp = 0;
    int arr_2[size];
    arr_2[size-1] = 0;
    set<int> check, uncheck;
    for (int i = size - 1; i > 0; i--) {
        auto it = check.find(arr[i]);
        if (it != check.end()) arr_2[i-1] = temp;
        else arr_2[i-1] = ++temp;
        check.insert(arr[i]);
    }
    for (int i = 0; i < size - 1; i++) {
        if (uncheck.find(arr[i]) != uncheck.end()) continue;
        count += arr_2[i];
        uncheck.insert(arr[i]);
    }
    return count;
}

int main() {
    int arr[] = {4, 3, 1, 6, 7};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout << "Count of unique pairs (arr[i], arr[j]) such that i < j are: " << unique_pair(arr, size);
    return 0;
}

Đầu ra

Count of unique pairs (arr[i], arr[j]) such that i < j are: 10