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

समस्या विवरण

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

उदाहरण

इनपुट

arr[] = {1, 2, 3, 4, 5, 5, 6, 7}

आउटपुट

5

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

विधि 1: रैखिक खोज (O(N))

समस्या को हल करने का एक सरल दृष्टिकोण रैखिक खोज का उपयोग करना है और जांचना है कि क्या arr[i] और arr[i+1] का मान समान है। इस मामले में, arr[i] वापस करें जो दोहराया गया मान है।

#include <iostream> 
using namespace std; 

int findRepeatingValueArr(int arr[], int N) {
    for(int i = 0; i < N - 1; i++) {
        if(arr[i] == arr[i+1])
            return arr[i];
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 4, 5, 6};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "सरणी में दोहराव वाला मान है " << findRepeatingValueArr(arr, N);
    return 0;
}

विधि 2: बाइनरी खोज (O(log N)) - इष्टतम

समस्या को हल करने का एक अन्य दृष्टिकोण बाइनरी खोज एल्गोरिदम का उपयोग करके मध्य इंडेक्स पर दो बार आने वाले तत्व को खोजना है। यदि मध्य इंडेक्स मान स्वयं को दोहराता है तो इसे प्रिंट करें। यदि यह इंडेक्स स्थिति पर नहीं है, तो दाएं उप-सरणी को पार करें अन्यथा बाएं उप-सरणी को पार करें।

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

int findRepeatingValueArr(int arr[], int start, int end) {
    if (start > end)
        return -1;
    
    int mid = (start + end) / 2;
    
    // यदि तत्व अपने अपेक्षित स्थिति पर नहीं है
    if (arr[mid] != mid + 1) {
        // जांचें कि क्या यह पिछले तत्व के साथ मेल खाता है
        if (mid > 0 && arr[mid] == arr[mid-1])
            return arr[mid];
        // बाएं आधे में खोजें
        return findRepeatingValueArr(arr, start, mid - 1);
    }
    // दाएं आधे में खोजें
    return findRepeatingValueArr(arr, mid + 1, end);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "सरणी में दोहराव वाला मान है " << findRepeatingValueArr(arr, 0, n-1);
    return 0;
}

आउटपुट

सरणी में दोहराव वाला मान है 6

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

बाइनरी खोज तर्क

एक क्रमबद्ध सरणी में जिसमें 1 से N-1 तक के तत्व और एक डुप्लिकेट होते हैं, तत्व i इंडेक्स i-1 पर होना चाहिए (1-आधारित)। यदि arr[mid] ≠ mid+1, तो डुप्लिकेट बाईं ओर है (या mid पर)। अन्यथा, यह दाईं ओर है।