በሁለቱም ድርድር ውስጥ ምንም ዓይነት የጋራ ንጥረ ነገር የሌለባቸውን አነስተኛ ንጥረ ነገሮችን ብዛት ያስወግዱ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የመርጨት MetLife ኦክሲጀን የኪስ ቦርሳ አገልግሎቱ Spotify
ሰልፍ ሃሽ

በቅደም ተከተል የ n እና m ንጥረ ነገሮችን ያካተቱ ሁለት ድርድር ሀ እና ቢ ተሰጥቷል ፡፡ በሁለቱም ውስጥ አንድ የተለመደ አካል እንዳይኖር አነስተኛውን የንጥሎች ብዛት ያስወግዱ ደርድር እና የተወገዱትን ንጥረ ነገሮች ብዛት ያትሙ።

ለምሳሌ  

ግቤት

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

ቢ [] = {1, 1}

ውጤት

ከእያንዲንደ ድርድር ሊወገዱ የሚችሏቸው አነስተኛ ንጥረ ነገሮች 3 ናቸው።

ዋናዉ ሀሣብ  

በሁለቱም ድርድሮች ውስጥ የተለመደ ንጥረ ነገር ቁጥር አለን እንበል ፡፡ ቁጥር በቁጥር A እና በ Y ብዛት ብዛት በድርድር ቢ ይታያል ስለዚህ የሁለቱን ድርድሮች መሻገሪያ ለማድረግ ፣ ሶስት አማራጮች አሉን

  1. የቁጥር ሁሉንም ክስተቶች ከድርድር ሀ ያስወግዱ።
  2. የቁጥር ሁሉንም ክስተቶች ከድርድር ቢ ያስወግዱ።
  3. አሁን ፣ የ ‹num› ሁሉንም ክስተቶች ከ A እና ለ ያስወግዱ ፡፡

አነስተኛውን የሥራ ክንዋኔ ማከናወን ስላለብን ከእነዚህ ሶስት አማራጮች ውስጥ 1 ን እንመርጣለንst X ከ Y ወይም 2 በታች ከሆነ አማራጭnd Y ከ X በታች ከሆነ አማራጭ።

በመደርደር ውስጥ የእያንዳንዱን ንጥረ ነገር ክስተቶች ለመቁጠር የሃሽ ሰንጠረዥን እንጠቀማለን ፡፡

አነስተኛውን የንጥሎች ብዛት ለማስወገድ አልጎሪዝም  

  1. መልሱን የሚያከማች ተለዋዋጭ አንስን ያስጀምሩ።
  2. በድርጊቶቹ ላይ ብስጭት እና የሁሉም ንጥረ ነገሮች ክስተት በሃሽ ጠረጴዛ ውስጥ ለሁለቱም ድርድሮች ያከማቹ ፡፡
  3. በድርጊቶቹ ውስጥ ለእያንዳንዱ ንጥረ ነገር ቁጥር ፣ ኤ በ ‹A› እና በ ‹‹›››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››››› ፡፡
  4. ተመለስ መልስ
ተመልከት
ከእያንዳንዱ ቁምፊ ምትክ ጥያቄ በኋላ ፓልንድሮምን ይፈትሹ

በምሳሌ ይረዱ  

አለን አለን እንበል

A [] = {2, 3, 2, 2, 0, 4}

ቢ [] = {4, 4, 2, 20}

አሁን ከላይ ላሉት ድርድሮች የሃሽ ሰንጠረዥን እናደርጋለን ፡፡

በሁለቱም ድርድር ውስጥ ምንም የተለመደ ንጥረ ነገር እንዳይኖር አነስተኛውን የንጥሎች ብዛት ያስወግዱ

ለኤለመንት 0 ፣ አናሶቹን አናሳውን (1 ፣ 0) = 0 እንጨምራለን ፡፡

ለኤለመንት 2 ፣ አናሶቹን አናሳውን (3 ፣ 1) = 1 እንጨምራለን ፡፡

አሁን ለኤለመንት 3 አናሶቹን አናሳውን (1 ፣ 0) = 0 እንጨምራለን ፡፡

ለኤለመንት 4 ፣ አናሶቹን አናሳውን (1 ፣ 2) = 1 እንጨምራለን ፡፡

ለኤለመንት 20 ፣ አናሶቹን አናሳውን (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

ውስብስብነት ትንተና ለ አነስተኛውን የንጥሎች ብዛት ያስወግዱ  

የጊዜ ውስብስብነት

በሁለቱም ድርድሮች ላይ አንድ ጊዜ ስናስቀምጥ ፣ ስለዚህ አጠቃላይ ጊዜ ውስብስብ ነው ኦ (N + M).

ተመልከት
የፊቦናቺ ቁጥሮችን በተቃራኒው ቅደም ተከተል ያትሙ

የቦታ ውስብስብነት

እኛ ሁለት ሃሽ ተጠቅመናል ሠንጠረዦች ለሁለቱም ድርድሮች የንጥረቶችን ድግግሞሽ ለማከማቸት ፣ ስለዚህ የቦታ ውስብስብነት ነው ኦ (N + M).

ማጣቀሻዎች