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

本文概述

  • 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

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

    推荐阅读