ऐसे तत्वों की न्यूनतम संख्या निकालें, जो दोनों ऐरे में कोई सामान्य तत्व मौजूद नहीं हैं


कठिनाई स्तर आसान
में अक्सर पूछा आलाप मेटलाइफ ऑक्सिजन वॉलेट अभी मरम्मत करें Spotify
ऐरे हैश

दो ए और बी क्रमशः एन और एम तत्वों से मिलकर दो सरणियों दिया। ऐसे तत्वों की न्यूनतम संख्या निकालें, जिनमें दोनों में कोई सामान्य तत्व मौजूद नहीं है सरणी और हटाए गए तत्वों की गिनती प्रिंट करें।

उदाहरण

इनपुट:

ए [] = {१, २, १, १}

बी [] = {१, १}

आउटपुट:

प्रत्येक सरणी से निकालने के लिए न्यूनतम तत्व 3 हैं।

मुख्य विचार

मान लीजिए कि हमारे पास एक तत्व संख्या है जो दोनों सरणियों में सामान्य है। संख्या सरणी A में Y की संख्या X और बार की संख्या X में दिखाई देती है। इसलिए दो सरणियों के चौराहे को अशक्त बनाने के लिए, हमारे पास तीन विकल्प हैं:

  1. सरणी A से संख्या की सभी आवृत्तियों को निकालें।
  2. सरणी B से संख्या की सभी आवृत्तियों को निकालें।
  3. अब, ए और बी दोनों से संख्या की सभी घटनाओं को हटा दें।

जैसा कि हमें न्यूनतम संचालन करना है, इन तीन विकल्पों में से, हम 1 चुनेंगेst विकल्प यदि X Y, या 2 से कम हैnd विकल्प यदि Y X से कम है।

सरणियों में प्रत्येक तत्व की घटनाओं को गिनने के लिए, हम हैश तालिका का उपयोग करेंगे।

तत्वों की न्यूनतम संख्या निकालें के लिए एल्गोरिथम

  1. एक वेरिएबल ans को इनिशियलाइज़ करें जो उत्तर को स्टोर करेगा।
  2. सरणियों पर Iterate करें और दोनों सरणियों के लिए हैश तालिका में प्रत्येक तत्व की घटना को संग्रहीत करें।
  3. सरणियों में प्रत्येक तत्व संख्या के लिए, यदि X A में संख्या के योग की संख्या है और Y, B में संख्या की घटना की संख्या है, तो ans में न्यूनतम (X, Y) जोड़ें।
  4. Ans लौटें।

एक उदाहरण से समझें

मान लीजिए कि हमारे पास है

ए [] = {२, ३, २, २, ०, ४}

बी [] = {४, ४, २, २०}

अब हम उपरोक्त सरणियों के लिए हैश तालिका बनाते हैं।

ऐसे तत्वों की न्यूनतम संख्या निकालें, जो दोनों सरणी में कोई सामान्य तत्व मौजूद नहीं हैं

तत्व 0 के लिए, हम ans में एक न्यूनतम (1, 0) = 0 जोड़ेंगे।

तत्व 2 के लिए, हम ans में एक न्यूनतम (3, 1) = 1 जोड़ेंगे।

अब, तत्व 3 के लिए, हम ans में एक न्यूनतम (1, 0) = 0 जोड़ेंगे।

तत्व 4 के लिए, हम ans में एक न्यूनतम (1, 2) = 1 जोड़ेंगे।

तत्व 20 के लिए, हम ans में एक न्यूनतम (0, 1) = 0 जोड़ेंगे।

अंतिम ans = 2।

तत्वों की न्यूनतम संख्या को हटाने के लिए C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
int MinElementsToRemove(vector<int> &A, vector<int> &B)
{
    unordered_map<int, int> count_A, count_B;
    for (auto ele : A)
    {
        count_A[ele]++;
    }
    for (auto ele : B)
    {
        count_B[ele]++;
    }
    int ans = 0;
    for (auto ele : count_A)
    {
        if (count_B.count(ele.first) == 1)
        {
            ans += min(count_B[ele.first], count_A[ele.first]);
        }
    }
    return ans;
}
int main()
{
    vector<int> A = {2, 3, 2, 2, 0, 4};
    vector<int> B = {4, 4, 2, 20};
    cout << "Minimum number of elements to remove from each array such that no common element exist in both array: " << MinElementsToRemove(A, B) << endl;
    return 0;
}
Minimum number of elements to remove from each array such that no common element exist between both array: 2

तत्वों की न्यूनतम संख्या को हटाने के लिए जावा कार्यक्रम

import java.util.*;
public class Main
{
    public static int MinElementsToRemove(int[] A, int[] B)
    {
        Map<Integer, Integer> count_A 
            = new HashMap<Integer, Integer>(); 
        Map<Integer, Integer> count_B
            = new HashMap<Integer, Integer>(); 
        for (int i=0; i<A.length;i++)
        {
            Integer j =count_A.get(A[i]); 
            count_A.put(A[i], (j == null) ? 1 : j + 1); 
        }
        for (int i=0; i<B.length;i++)
        {
            Integer j =count_B.get(B[i]); 
            count_B.put(B[i], (j == null) ? 1 : j + 1); 
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : count_A.entrySet()){
            if (count_B.get(entry.getKey())!=null)
            {
                ans += Math.min(count_B.get(entry.getKey()), count_A.get(entry.getKey()));
            }
        }
        return ans;
    }
  public static void main(String[] args) {
      int[] A = {2, 3, 2, 2, 0, 4};
        int[] B = {4, 4, 2, 20};
    System.out.println("Minimum number of elements to remove from each array such that no common element exist in both array: "+MinElementsToRemove(A, B));
  }
}


Minimum number of elements to remove from each array such that no common element exist between both array: 2

के लिए जटिलता विश्लेषण तत्वों की न्यूनतम संख्या निकालें

समय की जटिलता

जैसा कि हम दोनों सरणियों पर एक बार पुनरावृति करते हैं, इसलिए कुल समय जटिलता है O (N + M).

अंतरिक्ष की जटिलता

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

संदर्भ