给定三个按非降序排序的数组，打印这些数组中的所有公共元素。
null
例如：
输入 : ar1[]={1,5,10,20,40,80} ar2[]={6,7,20,80,100} ar3[]={3,4,15,20,30,70,80,120} 输出 : 20, 80
输入 : ar1[]={1,5,5} ar2[]={3,4,5,5,10} ar3[]={5,5,10,20} 输出 : 5, 5
一个简单的解决方法是首先找到 两个阵列的交集 并将交集存储在临时数组中，然后找到第三个数组和临时数组的交集。 这个解决方案的时间复杂度是 O（n1+n2+n3） 其中n1、n2和n3分别是ar1[]、ar2[]和ar3[]的尺寸。 上述解决方案需要额外的空间和两个循环，我们可以使用一个循环找到公共元素，而不需要额外的空间。这个想法类似于 两个阵列的交集 .就像两个数组循环一样，我们运行一个循环并遍历三个数组。 让在ar1[]中遍历的当前元素为x，在ar2[]中为y，在ar3[]中为z。
- 如果x、y和z是相同的，我们可以简单地将它们中的任何一个打印为公共元素，并在所有三个数组中继续前进。
- 否则，如果x
- 否则，如果x>z和y>z），我们可以简单地在ar3[]中前进，因为z不能是公共元素。
下图是上述方法的试运行：
以下是上述方法的实施情况：
C++
// C++ program to print common elements in three arrays #include <bits/stdc++.h> using namespace std; // This function prints common elements in ar1 void findCommon( int ar1[], int ar2[], int ar3[], int n1, int n2, int n3) { // Initialize starting indexes for ar1[], ar2[] and ar3[] int i = 0, j = 0, k = 0; // Iterate through three arrays while all arrays have elements while (i < n1 && j < n2 && k < n3) { // If x = y and y = z, print any of them and move ahead // in all arrays if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) { cout << ar1[i] << " " ; i++; j++; k++; } // x < y else if (ar1[i] < ar2[j]) i++; // y < z else if (ar2[j] < ar3[k]) j++; // We reach here when x > y and z < y, i.e., z is smallest else k++; } } // Driver code int main() { int ar1[] = {1, 5, 10, 20, 40, 80}; int ar2[] = {6, 7, 20, 80, 100}; int ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}; int n1 = sizeof (ar1)/ sizeof (ar1[0]); int n2 = sizeof (ar2)/ sizeof (ar2[0]); int n3 = sizeof (ar3)/ sizeof (ar3[0]); cout << "Common Elements are " ; findCommon(ar1, ar2, ar3, n1, n2, n3); return 0; } |
JAVA
// Java program to find common elements in three arrays class FindCommon { // This function prints common elements in ar1 void findCommon( int ar1[], int ar2[], int ar3[]) { // Initialize starting indexes for ar1[], ar2[] and ar3[] int i = 0 , j = 0 , k = 0 ; // Iterate through three arrays while all arrays have elements while (i < ar1.length && j < ar2.length && k < ar3.length) { // If x = y and y = z, print any of them and move ahead // in all arrays if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) { System.out.print(ar1[i]+ " " ); i++; j++; k++; } // x < y else if (ar1[i] < ar2[j]) i++; // y < z else if (ar2[j] < ar3[k]) j++; // We reach here when x > y and z < y, i.e., z is smallest else k++; } } // Driver code to test above public static void main(String args[]) { FindCommon ob = new FindCommon(); int ar1[] = { 1 , 5 , 10 , 20 , 40 , 80 }; int ar2[] = { 6 , 7 , 20 , 80 , 100 }; int ar3[] = { 3 , 4 , 15 , 20 , 30 , 70 , 80 , 120 }; System.out.print( "Common elements are " ); ob.findCommon(ar1, ar2, ar3); } } /*This code is contributed by Rajat Mishra */ |
python
# Python function to print common elements in three sorted arrays def findCommon(ar1, ar2, ar3, n1, n2, n3): # Initialize starting indexes for ar1[], ar2[] and ar3[] i, j, k = 0 , 0 , 0 # Iterate through three arrays while all arrays have elements while (i < n1 and j < n2 and k< n3): # If x = y and y = z, print any of them and move ahead # in all arrays if (ar1[i] = = ar2[j] and ar2[j] = = ar3[k]): print ar1[i], i + = 1 j + = 1 k + = 1 # x < y elif ar1[i] < ar2[j]: i + = 1 # y < z elif ar2[j] < ar3[k]: j + = 1 # We reach here when x > y and z < y, i.e., z is smallest else : k + = 1 # Driver program to check above function ar1 = [ 1 , 5 , 10 , 20 , 40 , 80 ] ar2 = [ 6 , 7 , 20 , 80 , 100 ] ar3 = [ 3 , 4 , 15 , 20 , 30 , 70 , 80 , 120 ] n1 = len (ar1) n2 = len (ar2) n3 = len (ar3) print "Common elements are" , findCommon(ar1, ar2, ar3, n1, n2, n3) # This code is contributed by __Devesh Agrawal__ |
C#
// C# program to find common elements in // three arrays using System; class GFG { // This function prints common element // s in ar1 static void findCommon( int []ar1, int []ar2, int []ar3) { // Initialize starting indexes for // ar1[], ar2[] and ar3[] int i = 0, j = 0, k = 0; // Iterate through three arrays while // all arrays have elements while (i < ar1.Length && j < ar2.Length && k < ar3.Length) { // If x = y and y = z, print any of // them and move ahead in all arrays if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) { Console.Write(ar1[i] + " " ); i++; j++; k++; } // x < y else if (ar1[i] < ar2[j]) i++; // y < z else if (ar2[j] < ar3[k]) j++; // We reach here when x > y and // z < y, i.e., z is smallest else k++; } } // Driver code to test above public static void Main() { int []ar1 = {1, 5, 10, 20, 40, 80}; int []ar2 = {6, 7, 20, 80, 100}; int []ar3 = {3, 4, 15, 20, 30, 70, 80, 120}; Console.Write( "Common elements are " ); findCommon(ar1, ar2, ar3); } } // This code is contributed by Sam007. |
PHP
<?php // PHP program to print common elements // in three arrays // This function prints common elements // in ar1 function findCommon( $ar1 , $ar2 , $ar3 , $n1 , $n2 , $n3 ) { // Initialize starting indexes for // ar1[], ar2[] and ar3[] $i = 0; $j = 0; $k = 0; // Iterate through three arrays while // all arrays have elements while ( $i < $n1 && $j < $n2 && $k < $n3 ) { // If x = y and y = z, print any // of them and move ahead in all // arrays if ( $ar1 [ $i ] == $ar2 [ $j ] && $ar2 [ $j ] == $ar3 [ $k ]) { echo $ar1 [ $i ] , " " ; $i ++; $j ++; $k ++; } // x < y else if ( $ar1 [ $i ] < $ar2 [ $j ]) $i ++; // y < z else if ( $ar2 [ $j ] < $ar3 [ $k ]) $j ++; // We reach here when x > y and // z < y, i.e., z is smallest else $k ++; } } // Driver program to test above function $ar1 = array (1, 5, 10, 20, 40, 80); $ar2 = array (6, 7, 20, 80, 100); $ar3 = array (3, 4, 15, 20, 30, 70, 80, 120); $n1 = count ( $ar1 ); $n2 = count ( $ar2 ); $n3 = count ( $ar3 ); echo "Common Elements are " ; findCommon( $ar1 , $ar2 , $ar3 , $n1 , $n2 , $n3 ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript program to print // common elements in three arrays // This function prints common elements in ar1 function findCommon(ar1, ar2, ar3, n1, n2, n3) { // Initialize starting indexes // for ar1[], ar2[] and ar3[] var i = 0, j = 0, k = 0; // Iterate through three arrays // while all arrays have elements while (i < n1 && j < n2 && k < n3) { // If x = y and y = z, print any of them and move ahead // in all arrays if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) { document.write(ar1[i] + " " ); i++; j++; k++; } // x < y else if (ar1[i] < ar2[j]) i++; // y < z else if (ar2[j] < ar3[k]) j++; // We reach here when x > y and z < y, i.e., z is smallest else k++; } } // Driver code var ar1 = [1, 5, 10, 20, 40, 80]; var ar2 = [6, 7, 20, 80, 100]; var ar3 = [3, 4, 15, 20, 30, 70, 80, 120]; var n1 = ar1.length; var n2 = ar2.length; var n3 = ar3.length; document.write( "Common Elements are " ); findCommon(ar1, ar2, ar3, n1, n2, n3); // This code is contributed by rdtank. </script> |
输出
Common Elements are 20 80
上述解决方案的时间复杂度为 O（n1+n2+n3） 。在最坏的情况下，最大大小的数组可能包含所有小元素，而中等大小的数组包含所有中间元素。
方法2 :
如果数组不包含重复的值，那么上面使用的方法可以很好地工作，但是在数组元素重复的情况下，它可能会失败。这可能会导致单个公共元素被打印多次。
通过跟踪上一个元素，可以在不使用任何额外数据结构的情况下处理这些重复条目。由于数组中的元素是按排序方式排列的，因此重复元素不可能出现在随机位置。
让我们考虑在AR1[]Be x中的当前元素，在AR2[]By和Ar3[]Bez中，让变量Prim1，Prim2，Prim3保持每个数组中最后一个遇到元素的轨迹，并用IntImin初始化它们。因此，对于每个数组中访问的每个元素，我们检查以下内容。
- 如果x=prev1，则在ar1[]中前进，并重复该过程，直到x！=1。同样，对ar2[]和ar3[]应用相同的方法。
- 如果x、y和z是相同的，我们可以简单地将它们中的任何一个打印为公共元素，更新prev1、prev2和prev3，并在所有三个数组中前进。
- 否则，如果（x
- 否则，如果（y
- 否则，如果（x>z和y>z），我们更新prev3，并在ar3[]中前进，因为z不能是公共元素。
- 否则，如果（y
以下是上述方法的实施情况：
C++
// C++ program to print common // elements in three arrays #include <bits/stdc++.h> using namespace std; // This function prints // common elements in ar1 void findCommon( int ar1[], int ar2[], int ar3[], int n1, int n2, int n3) { // Initialize starting indexes // for ar1[], ar2[] and // ar3[] int i = 0, j = 0, k = 0; // Declare three variables prev1, // prev2, prev3 to track // previous element int prev1, prev2, prev3; // Initialize prev1, prev2, // prev3 with INT_MIN prev1 = prev2 = prev3 = INT_MIN; // Iterate through three arrays // while all arrays have // elements while (i < n1 && j < n2 && k < n3) { // If ar1[i] = prev1 and i < n1, // keep incrementing i while (ar1[i] == prev1 && i < n1) i++; // If ar2[j] = prev2 and j < n2, // keep incrementing j while (ar2[j] == prev2 && j < n2) j++; // If ar3[k] = prev3 and k < n3, // keep incrementing k while (ar3[k] == prev3 && k < n3) k++; // If x = y and y = z, print // any of them, update // prev1 prev2, prev3 and move //ahead in each array if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) { cout << ar1[i] << " " ; prev1 = ar1[i]; prev2 = ar2[j]; prev3 = ar3[k]; i++; j++; k++; } // If x < y, update prev1 // and increment i else if (ar1[i] < ar2[j]) { prev1 = ar1[i]; i++; } // If y < z, update prev2 // and increment j else if (ar2[j] < ar3[k]) { prev2 = ar2[j]; j++; } // We reach here when x > y // and z < y, i.e., z is // smallest update prev3 // and imcrement k else { prev3 = ar3[k]; k++; } } } // Driver code int main() { int ar1[] = { 1, 5, 10, 20, 40, 80, 80 }; int ar2[] = { 6, 7, 20, 80, 80, 100 }; int ar3[] = { 3, 4, 15, 20, 30, 70, 80, 80, 120 }; int n1 = sizeof (ar1) / sizeof (ar1[0]); int n2 = sizeof (ar2) / sizeof (ar2[0]); int n3 = sizeof (ar3) / sizeof (ar3[0]); cout << "Common Elements are " ; findCommon(ar1, ar2, ar3, n1, n2, n3); return 0; } |
JAVA
// Java program to find common // elements in three arrays class FindCommon{ // This function prints common elements in ar1 void findCommon( int ar1[], int ar2[], int ar3[]) { // Initialize starting indexes for ar1[], // ar2[] and ar3[] int i = 0 , j = 0 , k = 0 ; int n1 = ar1.length; int n2 = ar2.length; int n3 = ar3.length; // Declare three variables prev1, // prev2, prev3 to track previous // element int prev1, prev2, prev3; // Initialize prev1, prev2, // prev3 with INT_MIN prev1 = prev2 = prev3 = Integer.MIN_VALUE; while (i < n1 && j < n2 && k < n3) { // If ar1[i] = prev1 and i < n1, // keep incrementing i while (i < n1 && ar1[i] == prev1) i++; // If ar2[j] = prev2 and j < n2, // keep incrementing j while (j < n2 && ar2[j] == prev2) j++; // If ar3[k] = prev3 and k < n3, // keep incrementing k while (k < n3 && ar3[k] == prev3) k++; if (i < n1 && j < n2 && k < n3) { // If x = y and y = z, print any of // them, update prev1 prev2, prev3 // and move ahead in each array if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) { System.out.print(ar1[i] + " " ); prev1 = ar1[i]; prev2 = ar2[j]; prev3 = ar3[k]; i++; j++; k++; } // If x < y, update prev1 // and increment i else if (ar1[i] < ar2[j]) { prev1 = ar1[i]; i++; } // If y < z, update prev2 // and increment j else if (ar2[j] < ar3[k]) { prev2 = ar2[j]; j++; } // We reach here when x > y // and z < y, i.e., z is // smallest update prev3 // and imcrement k else { prev3 = ar3[k]; k++; } } } } // Driver code public static void main(String args[]) { FindCommon ob = new FindCommon(); int ar1[] = { 1 , 5 , 10 , 20 , 40 , 80 , 80 }; int ar2[] = { 6 , 7 , 20 , 80 , 80 , 100 }; int ar3[] = { 3 , 4 , 15 , 20 , 30 , 70 , 80 , 80 , 120 }; System.out.print( "Common elements are " ); ob.findCommon(ar1, ar2, ar3); } } // This code is contributed by rajsanghavi9. |
Python3
# Python 3 program for above approach import sys # This function prints # common elements in ar1 def findCommon(ar1, ar2, ar3, n1, n2, n3) : # Initialize starting indexes # for ar1[], ar2and # ar3[] i = 0 j = 0 k = 0 # Declare three variables prev1, # prev2, prev3 to track # previous element # Initialize prev1, prev2, # prev3 with INT_MIN prev1 = prev2 = prev3 = - sys.maxsize - 1 # Iterate through three arrays # while all arrays have # elements while (i < n1 and j < n2 and k < n3) : # If ar1[i] = prev1 and i < n1, # keep incrementing i while (ar1[i] = = prev1 and i < n1 - 1 ) : i + = 1 # If ar2[j] = prev2 and j < n2, # keep incrementing j while (ar2[j] = = prev2 and j < n2) : j + = 1 # If ar3[k] = prev3 and k < n3, # keep incrementing k while (ar3[k] = = prev3 and k < n3) : k + = 1 # If x = y and y = z, pr # any of them, update # prev1 prev2, prev3 and move #ahead in each array if (ar1[i] = = ar2[j] and ar2[j] = = ar3[k]) : print (ar1[i],end = " " ) prev1 = ar1[i] prev2 = ar2[j] prev3 = ar3[k] i + = 1 j + = 1 k + = 1 # If x < y, update prev1 # and increment i elif (ar1[i] < ar2[j]) : prev1 = ar1[i] i + = 1 # If y < z, update prev2 # and increment j elif (ar2[j] < ar3[k]) : prev2 = ar2[j] j + = 1 # We reach here when x > y # and z < y, i.e., z is # smallest update prev3 # and imcrement k else : prev3 = ar3[k] k + = 1 # Driver code ar1 = [ 1 , 5 , 10 , 20 , 40 , 80 , 80 ] ar2 = [ 6 , 7 , 20 , 80 , 80 , 100 ] ar3 = [ 3 , 4 , 15 , 20 , 30 , 70 , 80 , 80 , 120 ] n1 = len (ar1) n2 = len (ar2) n3 = len (ar3) print ( "Common Elements are " ) findCommon(ar1, ar2, ar3, n1, n2, n3) # This code is contributed by splevel62. |
C#
// C# program to find common // elements in three arrays using System; class GFG{ // This function prints common elements in ar1 static void findCommon( int []ar1, int []ar2, int []ar3) { // Initialize starting indexes for ar1[], // ar2[] and ar3[] int i = 0, j = 0, k = 0; int n1 = ar1.Length; int n2 = ar2.Length; int n3 = ar3.Length; // Declare three variables prev1, // prev2, prev3 to track previous // element int prev1, prev2, prev3; // Initialize prev1, prev2, // prev3 with INT_MIN prev1 = prev2 = prev3 = Int32.MinValue; while (i < n1 && j < n2 && k < n3) { // If ar1[i] = prev1 and i < n1, // keep incrementing i while (i < n1 && ar1[i] == prev1) i++; // If ar2[j] = prev2 and j < n2, // keep incrementing j while (j < n2 && ar2[j] == prev2) j++; // If ar3[k] = prev3 and k < n3, // keep incrementing k while (k < n3 && ar3[k] == prev3) k++; if (i < n1 && j < n2 && k < n3) { // If x = y and y = z, print any of // them, update prev1 prev2, prev3 // and move ahead in each array if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) { Console.Write(ar1[i] + " " ); prev1 = ar1[i]; prev2 = ar2[j]; prev3 = ar3[k]; i++; j++; k++; } // If x < y, update prev1 // and increment i else if (ar1[i] < ar2[j]) { prev1 = ar1[i]; i++; } // If y < z, update prev2 // and increment j else if (ar2[j] < ar3[k]) { prev2 = ar2[j]; j++; } // We reach here when x > y // and z < y, i.e., z is // smallest update prev3 // and imcrement k else { prev3 = ar3[k]; k++; } } } } // Driver code public static void Main() { // FindCommon ob = new FindCommon(); int []ar1 = { 1, 5, 10, 20, 40, 80, 80 }; int []ar2 = { 6, 7, 20, 80, 80, 100 }; int []ar3 = { 3, 4, 15, 20, 30, 70, 80, 80, 120 }; Console.Write( "Common elements are " ); findCommon(ar1, ar2, ar3); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program to print common // elements in three arrays // This function prints // common elements in ar1 function findCommon(ar1, ar2, ar3, n1, n2, n3) { // Initialize starting indexes // for ar1[], ar2[] and // ar3[] var i = 0, j = 0, k = 0; // Declare three variables prev1, // prev2, prev3 to track // previous element var prev1, prev2, prev3; // Initialize prev1, prev2, // prev3 with INT_MIN prev1 = prev2 = prev3 = -1000000000; // Iterate through three arrays // while all arrays have // elements while (i < n1 && j < n2 && k < n3) { // If ar1[i] = prev1 and i < n1, // keep incrementing i while (ar1[i] == prev1 && i < n1) i++; // If ar2[j] = prev2 and j < n2, // keep incrementing j while (ar2[j] == prev2 && j < n2) j++; // If ar3[k] = prev3 and k < n3, // keep incrementing k while (ar3[k] == prev3 && k < n3) k++; // If x = y and y = z, print // any of them, update // prev1 prev2, prev3 and move //ahead in each array if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) { document.write(ar1[i] + " " ); prev1 = ar1[i]; prev2 = ar2[j]; prev3 = ar3[k]; i++; j++; k++; } // If x < y, update prev1 // and increment i else if (ar1[i] < ar2[j]) { prev1 = ar1[i]; i++; } // If y < z, update prev2 // and increment j else if (ar2[j] < ar3[k]) { prev2 = ar2[j]; j++; } // We reach here when x > y // and z < y, i.e., z is // smallest update prev3 // and imcrement k else { prev3 = ar3[k]; k++; } } } // Driver code var ar1 = [ 1, 5, 10, 20, 40, 80, 80 ]; var ar2 = [ 6, 7, 20, 80, 80, 100 ]; var ar3 = [ 3, 4, 15, 20, 30, 70, 80, 80, 120 ]; var n1 = ar1.length; var n2 = ar2.length; var n3 = ar3.length; document.write( "Common Elements are " ); findCommon(ar1, ar2, ar3, n1, n2, n3); </script> |
输出
Common Elements are 20 80
上述方法的时间复杂性仍然存在 O（n1+n2+n3） 空间复杂性也依然存在 O（1） 并且不需要额外的空间和数据结构来处理重复的数组条目。
方法3：
在这种方法中，我们将首先从每个数组中删除副本，然后，我们将找到每个元素的频率，并打印频率等于3的元素。为了找到频率，我们可以使用一个映射，但在这里，我们将使用数组而不是映射。但是使用数组的问题是，我们不能找到负数的频率，所以在下面给出的代码中，我们将考虑数组中的每个元素都是正的。
JAVA
// Java implementation of the above approach class GFG { public static void commonElements( int [] arr1, int [] arr2, int [] arr3, int n1, int n2, int n3) { // creating a max variable // for storing the maximum // value present in the all // the three array // this will be the size of // array for calculating the // frequency of each element // present in all the array int max = Integer.MIN_VALUE; // deleting duplicates in linear time // for arr1 int res1 = 1 ; for ( int i = 1 ; i < n1; i++) { max = Math.max(arr1[i], max); if (arr1[i] != arr1[res1 - 1 ]) { arr1[res1] = arr1[i]; res1++; } } // deleting duplicates in linear time // for arr2 int res2 = 1 ; for ( int i = 1 ; i < n2; i++) { max = Math.max(arr2[i], max); if (arr2[i] != arr2[res2 - 1 ]) { arr2[res2] = arr2[i]; res2++; } } // deleting duplicates in linear time // for arr3 int res3 = 1 ; for ( int i = 1 ; i < n3; i++) { max = Math.max(arr3[i], max); if (arr3[i] != arr3[res3 - 1 ]) { arr3[res3] = arr3[i]; res3++; } } // creating an array for finding frequency int [] freq = new int [max + 1 ]; // calculating the frequency of // all the elements present in // all the array for ( int i = 0 ; i < res1; i++) freq[arr1[i]]++; for ( int i = 0 ; i < res2; i++) freq[arr2[i]]++; for ( int i = 0 ; i < res3; i++) freq[arr3[i]]++; // iterating till max and // whenever the frequency of element // will be three we print that element for ( int i = 0 ; i <= max; i++) if (freq[i] == 3 ) System.out.print(i + " " ); } // Driver Code public static void main(String[] arg) { int arr1[] = { 1 , 5 , 10 , 20 , 40 , 80 }; int arr2[] = { 6 , 7 , 20 , 80 , 100 }; int arr3[] = { 3 , 4 , 15 , 20 , 30 , 70 , 80 , 120 }; commonElements(arr1, arr2, arr3, 6 , 5 , 8 ); } } |
C#
// C# implementation of the above approach using System; class GFG { public static void commonElements( int [] arr1, int [] arr2, int [] arr3, int n1, int n2, int n3) { // creating a max variable // for storing the maximum // value present in the all // the three array // this will be the size of // array for calculating the // frequency of each element // present in all the array int max = int .MinValue; // deleting duplicates in linear time // for arr1 int res1 = 1; for ( int i = 1; i < n1; i++) { max = Math.Max(arr1[i], max); if (arr1[i] != arr1[res1 - 1]) { arr1[res1] = arr1[i]; res1++; } } // deleting duplicates in linear time // for arr2 int res2 = 1; for ( int i = 1; i < n2; i++) { max = Math.Max(arr2[i], max); if (arr2[i] != arr2[res2 - 1]) { arr2[res2] = arr2[i]; res2++; } } // deleting duplicates in linear time // for arr3 int res3 = 1; for ( int i = 1; i < n3; i++) { max = Math.Max(arr3[i], max); if (arr3[i] != arr3[res3 - 1]) { arr3[res3] = arr3[i]; res3++; } } // creating an array for finding frequency int [] freq = new int [max + 1]; // calculating the frequency of // all the elements present in // all the array for ( int i = 0; i < res1; i++) freq[arr1[i]]++; for ( int i = 0; i < res2; i++) freq[arr2[i]]++; for ( int i = 0; i < res3; i++) freq[arr3[i]]++; // iterating till max and // whenever the frequency of element // will be three we print that element for ( int i = 0; i <= max; i++) if (freq[i] == 3) Console.Write(i + " " ); } // Driver Code public static void Main() { int [] arr1 = { 1, 5, 10, 20, 40, 80 }; int [] arr2 = { 6, 7, 20, 80, 100 }; int [] arr3 = { 3, 4, 15, 20, 30, 70, 80, 120 }; commonElements(arr1, arr2, arr3, 6, 5, 8); } } |
Javascript
<script> // javascript implementation of the above approach function commonElements(arr1, arr2, arr3 , n1 , n2 , n3) { // creating a max variable // for storing the maximum // value present in the all // the three array // this will be the size of // array for calculating the // frequency of each element // present in all the array var max = Number.MIN_VALUE; // deleting duplicates in linear time // for arr1 var res1 = 1; for ( var i = 1; i < n1; i++) { max = Math.max(arr1[i], max); if (arr1[i] != arr1[res1 - 1]) { arr1[res1] = arr1[i]; res1++; } } // deleting duplicates in linear time // for arr2 var res2 = 1; for ( var i = 1; i < n2; i++) { max = Math.max(arr2[i], max); if (arr2[i] != arr2[res2 - 1]) { arr2[res2] = arr2[i]; res2++; } } // deleting duplicates in linear time // for arr3 var res3 = 1; for ( var i = 1; i < n3; i++) { max = Math.max(arr3[i], max); if (arr3[i] != arr3[res3 - 1]) { arr3[res3] = arr3[i]; res3++; } } // creating an array for finding frequency var freq = Array(max + 1).fill(0); // calculating the frequency of // all the elements present in // all the array for (i = 0; i < res1; i++) freq[arr1[i]]++; for (i = 0; i < res2; i++) freq[arr2[i]]++; for (i = 0; i < res3; i++) freq[arr3[i]]++; // iterating till max and // whenever the frequency of element // will be three we print that element for (i = 0; i <= max; i++) if (freq[i] == 3) document.write(i + " " ); } // Driver Code var arr1 = [ 1, 5, 10, 20, 40, 80 ]; var arr2 = [ 6, 7, 20, 80, 100 ]; var arr3 = [ 3, 4, 15, 20, 30, 70, 80, 120 ]; commonElements(arr1, arr2, arr3, 6, 5, 8); // This code is contributed by Rajput-Ji </script> |
输出
20 80
方法4 ：使用STL
其想法是使用哈希集。这里我们使用其中两个集合来存储第一和第二数组的元素。然后检查第三个阵列的元素在前两组中是否存在。然后，我们使用第三个集合来防止任何重复项被添加到所需的数组中。
C++
#include <bits/stdc++.h> using namespace std; void findCommon( int a[], int b[], int c[], int n1, int n2, int n3) { // three sets to maintain frequency of elements unordered_set < int > uset,uset2,uset3; for ( int i=0;i<n1;i++){ uset.insert(a[i]); } for ( int i=0;i<n2;i++){ uset2.insert(b[i]); } // checking if elements of 3rd array are present in first 2 sets for ( int i=0;i<n3;i++){ if (uset.find(c[i])!=uset.end() && uset2.find(c[i])!=uset.end()){ // using a 3rd set to prevent duplicates if (uset3.find(c[i])==uset3.end()) cout<<c[i]<< " " ; uset3.insert(c[i]); } } } // Driver code int main() { int ar1[] = { 1, 5, 10, 20, 40, 80 }; int ar2[] = { 6, 7, 20, 80, 100 }; int ar3[] = { 3, 4, 15, 20, 30, 70, 80, 120 }; int n1 = sizeof (ar1) / sizeof (ar1[0]); int n2 = sizeof (ar2) / sizeof (ar2[0]); int n3 = sizeof (ar3) / sizeof (ar3[0]); cout << "Common Elements are " << endl; findCommon(ar1, ar2, ar3, n1, n2, n3); return 0; } |
Javascript
<script> function findCommon(a, b, c, n1, n2, n3) { // three sets to maintain frequency of elements let uset = new Set(); let uset2 = new Set(); let uset3 = new Set(); for (let i=0;i<n1;i++){ uset.add(a[i]); } for (let i=0;i<n2;i++){ uset2.add(b[i]); } // checking if elements of 3rd array are present in first 2 sets for (let i=0;i<n3;i++) { if (uset.has(c[i]) == true && uset2.has(c[i]) == true ) { // using a 3rd set to prevent duplicates if (uset3.has(c[i]) == false ) document.write(c[i], " " ); uset3.add(c[i]); } } } // Driver code let ar1 = [ 1, 5, 10, 20, 40, 80 ]; let ar2 = [ 6, 7, 20, 80, 100 ]; let ar3 = [ 3, 4, 15, 20, 30, 70, 80, 120 ]; let n1 = ar1.length; let n2 = ar2.length; let n3 = ar3.length; document.write( "Common Elements are " , "</br>" ); findCommon(ar1, ar2, ar3, n1, n2, n3); // This code is contributed by shinjanpatra. </script> |
输出
Common Elements are 20 80
时间复杂性： O（n1+n2+n3） 空间复杂性： O（n1+n2+n3）
本文由 古普塔 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
