C++ का उपयोग करके सरणी में एकमात्र अलग तत्व खोजना

समस्या विवरण

इस समस्या में, हमें आकार n की एक सरणी arr[] दी गई है। हमारा कार्य सरणी में एकमात्र अलग तत्व खोजना है।

सरणी में केवल दो अलग-अलग प्रकार के तत्व हैं। सभी तत्व समान हैं सिवाय एक के।

उदाहरण

इनपुट

arr[] = {1, 1, 1, 2, 1, 1, 1, 1}

आउटपुट

2

हल का दृष्टिकोण

समस्या को हल करने का एक सरल दृष्टिकोण सरणी को पार करना और उन तत्वों को खोजना है जो सरणी के अन्य तत्वों से अलग हैं। इस दृष्टिकोण को O(N²) समय जटिलता की आवश्यकता होती है।

O(N) में समस्या को हल करने का एक अन्य दृष्टिकोण हैश टेबल का उपयोग करके तत्वों और उनकी घटना आवृत्ति को संग्रहीत करना है। और एकल घटना आवृत्ति वाले मान को प्रिंट करना।

अनुकूलित O(N) दृष्टिकोण (स्थिर स्पेस)

चूंकि केवल दो अलग-अलग मान हैं और एक केवल एक बार आता है, हम पहले 3 तत्वों की जांच करके बहुमत तत्व निर्धारित कर सकते हैं, फिर अलग तत्व ढूंढ सकते हैं।

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

#include <iostream> 
using namespace std; 

int findDiffElementArray(int arr[], int n) {
    if (n == 1) return -1;
    if (n == 2) return arr[0];
    
    // पहले 3 तत्वों से बहुमत तत्व निर्धारित करें
    int majority;
    if (arr[0] == arr[1] || arr[0] == arr[2])
        majority = arr[0];
    else
        majority = arr[1];
    
    // अलग तत्व खोजें
    for (int i = 0; i < n; i++) {
        if (arr[i] != majority)
            return arr[i];
    }
    return -1;
}

int main() {
    int arr[] = {5, 5, 1, 5, 5, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "सरणी में अलग तत्व है " << findDiffElementArray(arr, n);
    return 0;
}

आउटपुट

सरणी में अलग तत्व है 1

जटिलता विश्लेषण

• समय जटिलता: O(N)
• स्पेस जटिलता: O(1)

वैकल्पिक: XOR दृष्टिकोण

यदि सरणी में सभी तत्व दो बार आते हैं सिवाय एक के, तो XOR काम करता है। लेकिन यहां पैटर्न अलग है (एक तत्व एक बार, अन्य सभी कई बार)।