给定两组整数作为大小为m和n的两个数组。查找应从集合中移除的最小数的计数，以便两个集合不相交或不包含任何公共元素。我们可以从任何集合中删除元素。我们需要找到要移除的最小元素总数。 例如：
null
Input : set1[] = {20, 21, 22} set2[] = {22, 23, 24, 25}Output : 1We need to remove at least 1 elementwhich is 22 from set1 to make two sets disjoint.Input : set1[] = {20, 21, 22} set2[] = {22, 23, 24, 25, 20}Output : 2Input : set1[] = {6, 7} set2[] = {12, 13, 14, 15}Output : 0
如果我们仔细研究这个问题，我们可以发现这个问题归结为寻找两个集合的交集。 A. 简单解决方案 迭代第一个集合中的每个元素，对于每个元素，检查它是否存在于第二个集合中。如果存在，则增加要删除的元素数。
C++
// C++ simple program to find total elements // to be removed to make two sets disjoint. #include<bits/stdc++.h> using namespace std; // Function for find minimum elements to be // removed from both sets so that they become // disjoint int makeDisjoint( int set1[], int set2[], int n, int m) { int result = 0; for ( int i=0; i<n; i++) { int j; for (j=0; j<m; j++) if (set1[i] == set2[j]) break ; if (j != m) result++; } return result; } // Driven code int main() { int set1[] = {20, 21, 22}; int set2[] = {22, 23, 24, 25, 20}; int n = sizeof (set1)/ sizeof (set1[0]); int m = sizeof (set2)/ sizeof (set2[1]); cout << makeDisjoint(set1, set2, n, m); return 0; } |
JAVA
// Java simple program to find // total elements to be removed // to make two sets disjoint. import java.io.*; public class GFG{ // Function for find minimum elements // to be removed from both sets // so that they become disjoint static int makeDisjoint( int []set1, int []set2, int n, int m) { int result = 0 ; for ( int i = 0 ; i < n; i++) { int j; for (j = 0 ; j < m; j++) if (set1[i] == set2[j]) break ; if (j != m) result++; } return result; } // Driver code static public void main (String[] args) { int []set1 = { 20 , 21 , 22 }; int []set2 = { 22 , 23 , 24 , 25 , 20 }; int n = set1.length; int m = set2.length; System.out.println(makeDisjoint(set1, set2, n, m)); } } // This code is contributed by vt_m. |
Python 3
# Python 3 simple program to find # total elements to be removed to # make two sets disjoint. # Function for find minimum elements # to be removed from both sets so that # they become disjoint def makeDisjoint(set1, set2, n, m): result = 0 ; for i in range ( 0 , n - 1 ): for j in range ( 0 , m - 1 ): if (set1[i] = = set2[j]): break if (j ! = m): result + = 1 return result # Driver Code set1 = [ 20 , 21 , 22 ] set2 = [ 22 , 23 , 24 , 25 , 20 ] n = len (set1) m = len (set2) print (makeDisjoint(set1, set2, n, m)) # This code is contributed # by Akanksha Rai |
C#
// C# simple program to find // total elements to be removed // to make two sets disjoint. using System; public class GFG{ // Function for find minimum elements // to be removed from both sets // so that they become disjoint static int makeDisjoint( int []set1, int []set2, int n, int m) { int result = 0; for ( int i = 0; i < n; i++) { int j; for (j = 0; j < m; j++) if (set1[i] == set2[j]) break ; if (j != m) result++; } return result; } // Driver code static public void Main () { int []set1 = {20, 21, 22}; int []set2 = {22, 23, 24, 25, 20}; int n = set1.Length; int m = set2.Length; Console.WriteLine(makeDisjoint(set1, set2, n, m)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP simple program to find // total elements to be removed // to make two sets disjoint. // Function for find minimum // elements to be removed from // both sets so that they become disjoint function makeDisjoint( $set1 , $set2 , $n , $m ) { $result = 0; for ( $i = 0; $i < $n ; $i ++) { $j ; for ( $j = 0; $j < $m ; $j ++) if ( $set1 [ $i ] == $set2 [ $j ]) break ; if ( $j != $m ) $result ++; } return $result ; } // Driven code $set1 = array (20, 21, 22); $set2 = array (22, 23, 24, 25, 20); $n = count ( $set1 ); $m = count ( $set2 ); echo makeDisjoint( $set1 , $set2 , $n , $m ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript simple program to find // total elements to be removed // to make two sets disjoint. // Function for find minimum elements // to be removed from both sets // so that they become disjoint function makeDisjoint(set1,set2,n,m) { let result = 0; for (let i = 0; i < n; i++) { let j; for (j = 0; j < m; j++) if (set1[i] == set2[j]) break ; if (j != m) result++; } return result; } // Driver code let set1=[20, 21, 22]; let set2=[22, 23, 24, 25, 20]; let n = set1.length; let m = set2.length; document.write(makeDisjoint(set1, set2, n, m)); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
2
时间复杂性： O（m*n） 辅助空间： O（1） 一 有效解决方案 就是使用散列。我们创建一个空散列，并在其中插入集合1的所有项。现在遍历集合2，检查每个元素是否存在哈希。如果存在，则增加要删除的元素数。
C++
// C++ efficient program to find total elements // to be removed to make two sets disjoint. #include<bits/stdc++.h> using namespace std; // Function for find minimum elements to be // removed from both sets so that they become // disjoint int makeDisjoint( int set1[], int set2[], int n, int m) { // Store all elements of first array in a hash // table unordered_set < int > s; for ( int i = 0; i < n; i++) s.insert(set1[i]); // We need to remove all those elements from // set2 which are in set1. int result = 0; for ( int i = 0; i < m; i++) if (s.find(set2[i]) != s.end()) result++; return result; } // Driver code int main() { int set1[] = {20, 21, 22}; int set2[] = {22, 23, 24, 25, 20}; int n = sizeof (set1)/ sizeof (set1[0]); int m = sizeof (set2)/ sizeof (set2[1]); cout << makeDisjoint(set1, set2, n, m); return 0; } |
JAVA
// Java efficient program to find total elements // to be removed to make two sets disjoint. import java.util.*; class GFG { // Function for find minimum elements to be // removed from both sets so that they become // disjoint static int makeDisjoint( int set1[], int set2[], int n, int m) { // Store all elements of first array in a hash // table LinkedHashSet<Integer> s = new LinkedHashSet<Integer>(); for ( int i = 0 ; i < n; i++) { s.add(set1[i]); } // We need to remove all those elements from // set2 which are in set1. int result = 0 ; for ( int i = 0 ; i < m; i++) { if (s.contains(set2[i])) { result++; } } return result; } // Driver code public static void main(String[] args) { int set1[] = { 20 , 21 , 22 }; int set2[] = { 22 , 23 , 24 , 25 , 20 }; int n = set1.length; int m = set2.length; System.out.println(makeDisjoint(set1, set2, n, m)); } } // This code is contributed by PrinciRaj1992 |
Python 3
# Python 3 efficient program to find # total elements to be removed to # make two sets disjoint. # Function for find minimum elements # to be removed from both sets so # that they become disjoint def makeDisjoint(set1, set2, n, m): # Store all elements of first array # in a hash table s = [] for i in range (n): s.append(set1[i]) # We need to remove all those elements # from set2 which are in set1. result = 0 for i in range (m): if set2[i] in s: result + = 1 return result # Driver code if __name__ = = "__main__" : set1 = [ 20 , 21 , 22 ] set2 = [ 22 , 23 , 24 , 25 , 20 ] n = len (set1) m = len (set2) print (makeDisjoint(set1, set2, n, m)) # This code is contributed # by ChitraNayal |
C#
// C# efficient program to find total elements // to be removed to make two sets disjoint. using System; using System.Collections.Generic; class GFG { // Function for find minimum elements to be // removed from both sets so that they become // disjoint static int makeDisjoint( int []set1, int []set2, int n, int m) { // Store all elements of first array in a hash // table HashSet< int > s = new HashSet< int >(); for ( int i = 0; i < n; i++) { s.Add(set1[i]); } // We need to remove all those elements from // set2 which are in set1. int result = 0; for ( int i = 0; i < m; i++) { if (s.Contains(set2[i])) { result++; } } return result; } // Driver code public static void Main(String[] args) { int []set1 = {20, 21, 22}; int []set2 = {22, 23, 24, 25, 20}; int n = set1.Length; int m = set2.Length; Console.WriteLine(makeDisjoint(set1, set2, n, m)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to find total elements // to be removed to make two sets disjoint. // Function for find minimum elements to be // removed from both sets so that they become // disjoint function makeDisjoint(set1, set2, n, m) { // Store all elements of first array in a hash // table let s = new Set(); for (let i = 0; i < n; i++) { s.add(set1[i]); } // We need to remove all those elements from // set2 which are in set1. let result = 0; for (let i = 0; i < m; i++) { if (s.has(set2[i])) { result++; } } return result; } // Driver code let set1 = [20, 21, 22]; let set2 = [22, 23, 24, 25, 20]; let n = set1.length; let m = set2.length; document.write(makeDisjoint(set1, set2, n, m)); </script> |
输出：
2
时间复杂性： O（m+n） 辅助空间： O（m） 本文由 斯马拉科普达尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
