C++ का उपयोग करके दिए गए तत्वों को हटाने के बाद सबसे छोटा तत्व खोजें

समस्या विवरण

इस समस्या में, हमें दो सरणियाँ arr[] और del[] दी गई हैं। हमारा कार्य दिए गए तत्वों को हटाने के बाद सबसे छोटा तत्व खोजना है।

हम arr[] सरणी से उन मानों को हटाएंगे जो del[] में मौजूद हैं। और फिर हटाने के बाद सबसे छोटा मान प्रिंट करेंगे।

उदाहरण

इनपुट

arr[] = {2, 5, 6, 9, 1}
del[] = {1, 5, 9}

आउटपुट

2

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

इस समस्या का एक सरल समाधान हैशिंग का उपयोग करना है। हम del[] सरणी के सभी मानों को हैश टेबल में डालेंगे। फिर हम arr[] सरणी को पार करेंगे और जांचेंगे कि क्या मान हैश टेबल में है। यदि यह minVal से छोटा है, तो minVal प्रिंट करें।

एल्गोरिदम

1. del[] के सभी तत्वों को एक अनऑर्डर्ड मैप (हैश टेबल) में उनकी आवृत्ति के साथ संग्रहीत करें
2. arr[] को पार करें:
   • यदि वर्तमान तत्व हैश टेबल में है, तो उसकी आवृत्ति घटाएं और यदि 0 हो जाए तो हटा दें
   • अन्यथा, minVal को अपडेट करें
3. minVal वापस करें

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

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

int findSmallestVal(int arr[], int m, int del[], int n) {
    unordered_map<int, int> delVals;
    
    // del[] के तत्वों को हैश टेबल में डालें
    for (int i = 0; i < n; ++i) {
        delVals[del[i]]++;
    }
    
    int minVal = INT_MAX;
    
    // arr[] को पार करें
    for (int i = 0; i < m; ++i) {
        if (delVals.find(arr[i]) != delVals.end()) {
            // तत्व हटाने के लिए है
            delVals[arr[i]]--;
            if (delVals[arr[i]] == 0)
                delVals.erase(arr[i]);
        } else {
            // तत्व रखें, न्यूनतम अपडेट करें
            minVal = min(minVal, arr[i]);
        }
    }
    
    return minVal;
}

int main() {
    int array[] = {5, 12, 33, 4, 56, 12, 20};
    int m = sizeof(array) / sizeof(array[0]);
    int del[] = {12, 4, 56, 5};
    int n = sizeof(del) / sizeof(del[0]);
    
    cout << "हटाने के बाद सबसे छोटा मान " << findSmallestVal(array, m, del, n);
    return 0;
}

आउटपुट

हटाने के बाद सबसे छोटा मान 12

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

• समय जटिलता: O(m + n) - औसत स्थिति में
• स्पेस जटिलता: O(n) - हैश टेबल के लिए

टिप्पणी

यह दृष्टिकोण del[] में डुप्लिकेट मानों को सही ढंग से संभालता है। प्रत्येक घटना arr[] से एक मिलान तत्व को हटा देती है।