सरणी में अद्वितीय जोड़े (arr[i], arr[j]) जहाँ i < j - C++

समस्या विवरण

हमें एक पूर्णांक सरणी दी गई है। लक्ष्य उन अद्वितीय जोड़ों (arr[i], arr[j]) की गणना करना है जहाँ i < j।

उदाहरण

इनपुट: arr[] = {1,2,3}

आउटपुट: 3

व्याख्या: (1,2), (1,3), (2,3)

इनपुट: arr[] = {4,4,3,2}

आउटपुट: 4

व्याख्या: (4,4), (4,3), (4,2), (3,2)

दृष्टिकोण

साधारण: दो नेस्टेड लूप से सभी जोड़े set> में डालें। सेट का आकार उत्तर है।

कुशल: प्रत्येक इंडेक्स i के लिए, i के बाद आने वाले अद्वितीय तत्वों की संख्या गिनें। दाएँ से बाएँ पार करके arr_2[i] = i के बाद के अद्वितीय तत्वों की संख्या स्टोर करें। फिर बाएँ से दाएँ पार करके पहली बार आने वाले प्रत्येक तत्व के लिए arr_2[i] जोड़ें।

एल्गोरिदम (कुशल)

1. arr_2[size-1] = 0
2. दाएँ से बाएँ: check सेट में arr[i] खोजें। यदि नहीं मिला तो temp++ और arr_2[i-1] = temp, अन्यथा arr_2[i-1] = temp
3. check में arr[i] डालें
4. बाएँ से दाएँ: uncheck सेट में arr[i] खोजें। यदि नहीं मिला तो count += arr_2[i]
5. uncheck में arr[i] डालें
6. count लौटाएँ

C++ कार्यान्वयन

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

// कुशल दृष्टिकोण
int unique_pair(int arr[], int size) {
    int count = 0, temp = 0;
    vector arr_2(size);
    arr_2[size-1] = 0;
    unordered_set check, uncheck;
    
    for (int i = size - 1; i > 0; i--) {
        if (check.find(arr[i]) != 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: " << unique_pair(arr, size);
    return 0;
}

आउटपुट

Count: 10