移除最小数量的元素，使两个数组中不存在公共元素

本文概述

• C ++
• Java
• Python3
• C#

给定两个分别由n和m个元素组成的数组A []和B []。找到要从每个数组中删除的最小元素数, 以使两个元素中都不存在公共元素。

例子：

Input : A[] = { 1, 2, 3, 4}
        B[] = { 2, 3, 4, 5, 8 }
Output : 3
We need to remove 2, 3 and 4 from any array.

Input : A[] = { 4, 2, 4, 4}
        B[] = { 4, 3 }
Output : 1
We need to remove 4 from B[]

Input : A[] = { 1, 2, 3, 4 }
        B[] = { 5, 6, 7 }
Output : 0
There is no common element in both.

计算两个数组中每个数字的出现。如果两个数组中都有数字, 则从出现次数减少的数组中删除数字, 将其添加到结果中。

C ++

// CPP program to find minimum element
// to remove so no common element
// exist in both array
#include <bits/stdc++.h>
using namespace std;
  
// To find no elements to remove
// so no common element exist
int minRemove( int a[], int b[], int n, int m)
{
     // To store count of array element
     unordered_map< int , int > countA, countB;
  
     // Count elements of a
     for ( int i = 0; i < n; i++)
         countA[a[i]]++;
  
     // Count elements of b
     for ( int i = 0; i < m; i++)
         countB[b[i]]++;
  
     // Traverse through all common element, and
     // pick minimum occurrence from two arrays
     int res = 0;
     for ( auto x : countA)
         if (countB.find(x.first) != countB.end())
             res += min(x.second, countB[x.first]);
  
     // To return count of minimum elements
     return res;
}
  
// Driver program to test minRemove()
int main()
{
     int a[] = { 1, 2, 3, 4 };
     int b[] = { 2, 3, 4, 5, 8 };
     int n = sizeof (a) / sizeof (a[0]);
     int m = sizeof (b) / sizeof (b[0]);
  
     cout << minRemove(a, b, n, m);
  
     return 0;
}

Java

// JAVA Code to Remove minimum number of elements
// such that no common element exist in both array
import java.util.*;
  
class GFG {
      
     // To find no elements to remove
     // so no common element exist
     public static int minRemove( int a[], int b[], int n, int m)
     {
         // To store count of array element
         HashMap<Integer, Integer> countA = new HashMap<
                                           Integer, Integer>();
         HashMap<Integer, Integer> countB = new HashMap<
                                           Integer, Integer>();
       
         // Count elements of a
         for ( int i = 0 ; i < n; i++){
            if (countA.containsKey(a[i]))
                 countA.put(a[i], countA.get(a[i]) + 1 );
             
            else countA.put(a[i], 1 );
                 
         }
          
         // Count elements of b
         for ( int i = 0 ; i < m; i++){
              if (countB.containsKey(b[i]))
                     countB.put(b[i], countB.get(b[i]) + 1 );
                 
                else countB.put(b[i], 1 );
         }
          
         // Traverse through all common element, and
         // pick minimum occurrence from two arrays
         int res = 0 ;
          
         Set<Integer> s = countA.keySet();
          
         for ( int x : s)
             if (countB.containsKey(x))
                 res += Math.min(countB.get(x), countA.get(x));
       
         // To return count of minimum elements
         return res;
     }
      
     /* Driver program to test above function */
     public static void main(String[] args) 
     {
  
             int a[] = { 1 , 2 , 3 , 4 };
             int b[] = { 2 , 3 , 4 , 5 , 8 };
             int n = a.length;
             int m = b.length;
           
             System.out.println(minRemove(a, b, n, m));
              
     }
}
    
// This code is contributed by Arnav Kr. Mandal.

Python3

# Python3 program to find minimum 
# element to remove so no common 
# element exist in both array
  
# To find no elements to remove
# so no common element exist
def minRemove(a, b, n, m):
  
     # To store count of array element
     countA = dict ()
     countB = dict ()
  
     # Count elements of a
     for i in range (n):
         countA[a[i]] = countA.get(a[i], 0 ) + 1
  
     # Count elements of b
     for i in range (n):
         countB[b[i]] = countB.get(b[i], 0 ) + 1
  
     # Traverse through all common 
     # element, and pick minimum 
     # occurrence from two arrays
     res = 0
     for x in countA:
         if x in countB.keys():
             res + = min (countA[x], countB[x])
  
     # To return count of
     # minimum elements
     return res
  
# Driver Code
a = [ 1 , 2 , 3 , 4 ]
b = [ 2 , 3 , 4 , 5 , 8 ]
n = len (a)
m = len (b)
print (minRemove(a, b, n, m))
  
# This code is contributed 
# by mohit kumar

C#

// C# Code to Remove minimum number of elements
// such that no common element exist in both array
using System;
using System.Collections.Generic;
  
class GFG
{
      
     // To find no elements to remove
     // so no common element exist
     public static int minRemove( int []a, int []b, int n, int m)
     {
         // To store count of array element
         Dictionary< int , int > countA = new Dictionary< int , int >();
         Dictionary< int , int >countB = new Dictionary< int , int >();
      
         // Count elements of a
         for ( int i = 0; i < n; i++)
         {
             if (countA.ContainsKey(a[i]))
             {
                 var v = countA[a[i]];
                 countA.Remove(countA[a[i]]);
                 countA.Add(a[i], v + 1);
             }
             else countA.Add(a[i], 1);
                  
         }   
          
         // Count elements of b
         for ( int i = 0; i < m; i++)
         {
             if (countB.ContainsKey(b[i]))
             {
                 var v = countB[b[i]];
                 countB.Remove(countB[b[i]]);
                 countB.Add(b[i], v + 1);
             } 
             else countB.Add(b[i], 1);
         }
          
         // Traverse through all common element, and
         // pick minimum occurrence from two arrays
         int res = 0;
  
         foreach ( int x in countA.Keys)
             if (countB.ContainsKey(x))
                 res += Math.Min(countB[x], countA[x]);
      
         // To return count of minimum elements
         return res;
     }
      
     /* Driver code */
     public static void Main(String[] args) 
     {
  
             int []a = { 1, 2, 3, 4 };
             int []b = { 2, 3, 4, 5, 8 };
             int n = a.Length;
             int m = b.Length;
          
             Console.WriteLine(minRemove(a, b, n, m));
     }
}
  
// This code has been contributed by 29AjayKumar

输出如下：

3

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。