两个排序数组的并集和交集-yiteyi-C++库

给定两个排序数组，找到它们的并集和交集。

null

例子：

Input : arr1[] = {1, 3, 4, 5, 7}        arr2[] = {2, 3, 5, 6} Output : Union : {1, 2, 3, 4, 5, 6, 7}          Intersection : {3, 5}Input : arr1[] = {2, 5, 6}        arr2[] = {4, 6, 8, 10} Output : Union : {2, 4, 5, 6, 8, 10}          Intersection : {6}

我们强烈建议您在继续解决方案之前单击此处并进行练习。

数组arr1[]和arr2[]的并集

要查找两个已排序数组的并集，请执行以下合并过程：

1）使用两个索引变量i和j，初始值i=0，j=0 2）如果arr1[i]小于arr2[j]，则打印arr1[i]和增量i。 3）如果arr1[i]大于arr2[j]，则打印arr2[j]并增加j。 4）如果两者相同，则打印其中任何一个并增加i和j。 5）打印较大数组的剩余元素。

以下是上述方法的实施情况：

C++

                         // C++ program to find union of                       
                         // two sorted arrays                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         /* Function prints union of arr1[] and arr2[]                       
                                                 m is the number of elements in arr1[]                       
                                                 n is the number of elements in arr2[] */                       
                         void                                     printUnion(                                     int                                     arr1[],                                     int                                     arr2[],                                     int                                     m,                                     int                                     n)                       
                         {                       
                                                 int                                     i = 0, j = 0;                       
                                                 while                                     (i < m && j < n) {                       
                                                 if                                     (arr1[i] < arr2[j])                       
                                                 cout << arr1[i++] <<                                     " "                                     ;                       
           
                                                 else                                     if                                     (arr2[j] < arr1[i])                       
                                                 cout << arr2[j++] <<                                     " "                                     ;                       
           
                                                 else                                     {                       
                                                 cout << arr2[j++] <<                                     " "                                     ;                       
                                                 i++;                       
                                                 }                       
                                                 }                       
           
                                                 /* Print remaining elements of the larger array */                       
                                                 while                                     (i < m)                       
                                                 cout << arr1[i++] <<                                     " "                                     ;                       
           
                                                 while                                     (j < n)                       
                                                 cout << arr2[j++] <<                                     " "                                     ;                       
                         }                       
           
                         /* Driver program to test above function */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr1[] = { 1, 2, 4, 5, 6 };                       
                                                 int                                     arr2[] = { 2, 3, 5, 7 };                       
           
                                                 int                                     m =                                     sizeof                                     (arr1) /                                     sizeof                                     (arr1[0]);                       
                                                 int                                     n =                                     sizeof                                     (arr2) /                                     sizeof                                     (arr2[0]);                       
           
                                                 // Function calling                       
                                                 printUnion(arr1, arr2, m, n);                       
           
                                                 return                                     0;                       
                         }                       

C

                         // C program to find union of                       
                         // two sorted arrays                       
                         #include <stdio.h>                       
           
                         /* Function prints union of arr1[] and arr2[]                       
                                                 m is the number of elements in arr1[]                       
                                                 n is the number of elements in arr2[] */                       
                         void                                     printUnion(                                     int                                     arr1[],                                     int                                     arr2[],                                     int                                     m,                                     int                                     n)                       
                         {                       
                                                 int                                     i = 0, j = 0;                       
                                                 while                                     (i < m && j < n) {                       
                                                 if                                     (arr1[i] < arr2[j])                       
                                                 printf                                     (                                     " %d "                                     , arr1[i++]);                       
                                                 else                                     if                                     (arr2[j] < arr1[i])                       
                                                 printf                                     (                                     " %d "                                     , arr2[j++]);                       
                                                 else                                     {                       
                                                 printf                                     (                                     " %d "                                     , arr2[j++]);                       
                                                 i++;                       
                                                 }                       
                                                 }                       
           
                                                 /* Print remaining elements of the larger array */                       
                                                 while                                     (i < m)                       
                                                 printf                                     (                                     " %d "                                     , arr1[i++]);                       
                                                 while                                     (j < n)                       
                                                 printf                                     (                                     " %d "                                     , arr2[j++]);                       
                         }                       
           
                         /* Driver program to test above function */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr1[] = { 1, 2, 4, 5, 6 };                       
                                                 int                                     arr2[] = { 2, 3, 5, 7 };                       
                                                 int                                     m =                                     sizeof                                     (arr1) /                                     sizeof                                     (arr1[0]);                       
                                                 int                                     n =                                     sizeof                                     (arr2) /                                     sizeof                                     (arr2[0]);                       
                                                 printUnion(arr1, arr2, m, n);                       
                                                 getchar                                     ();                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find union of                       
                         // two sorted arrays                       
           
                         class                                     FindUnion {                       
                                                 /* Function prints union of arr1[] and arr2[]                       
                                                 m is the number of elements in arr1[]                       
                                                 n is the number of elements in arr2[] */                       
                                                 static                                     int                                     printUnion(                                     int                                     arr1[],                                     int                                     arr2[],                                     int                                     m,                                     int                                     n)                       
                                                 {                       
                                                 int                                     i =                                     0                                     , j =                                     0                                     ;                       
                                                 while                                     (i < m && j < n) {                       
                                                 if                                     (arr1[i] < arr2[j])                       
                                                 System.out.print(arr1[i++] +                                     " "                                     );                       
                                                 else                                     if                                     (arr2[j] < arr1[i])                       
                                                 System.out.print(arr2[j++] +                                     " "                                     );                       
                                                 else                                     {                       
                                                 System.out.print(arr2[j++] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                                 }                       
           
                                                 /* Print remaining elements of                       
                                                 the larger array */                       
                                                 while                                     (i < m)                       
                                                 System.out.print(arr1[i++] +                                     " "                                     );                       
                                                 while                                     (j < n)                       
                                                 System.out.print(arr2[j++] +                                     " "                                     );                       
           
                                                 return                                     0                                     ;                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     arr1[] = {                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     };                       
                                                 int                                     arr2[] = {                                     2                                     ,                                     3                                     ,                                     5                                     ,                                     7                                     };                       
                                                 int                                     m = arr1.length;                       
                                                 int                                     n = arr2.length;                       
                                                 printUnion(arr1, arr2, m, n);                       
                                                 }                       
                         }                       

蟒蛇3

                         # Python program to find union of                       
                         # two sorted arrays                       
                         # Function prints union of arr1[] and arr2[]                       
                         # m is the number of elements in arr1[]                       
                         # n is the number of elements in arr2[]                       
                         def                                     printUnion(arr1, arr2, m, n):                       
                                                 i, j                                     =                                     0                                     ,                                     0                       
                                                 while                                     i < m                                     and                                     j < n:                       
                                                 if                                     arr1[i] < arr2[j]:                       
                                                 print                                     (arr1[i],end                                     =                                     " "                                     )                       
                                                 i                                     +                                     =                                     1                       
                                                 elif                                     arr2[j] < arr1[i]:                       
                                                 print                                     (arr2[j],end                                     =                                     " "                                     )                       
                                                 j                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 print                                     (arr2[j],end                                     =                                     " "                                     )                       
                                                 j                                     +                                     =                                     1                       
                                                 i                                     +                                     =                                     1                       
           
                                                 # Print remaining elements of the larger array                       
                                                 while                                     i < m:                       
                                                 print                                     (arr1[i],end                                     =                                     " "                                     )                       
                                                 i                                     +                                     =                                     1                       
           
                                                 while                                     j < n:                       
                                                 print                                     (arr2[j],end                                     =                                     " "                                     )                       
                                                 j                                     +                                     =                                     1                       
           
                         # Driver program to test above function                       
                         arr1                                     =                                     [                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ]                       
                         arr2                                     =                                     [                                     2                                     ,                                     3                                     ,                                     5                                     ,                                     7                                     ]                       
                         m                                     =                                     len                                     (arr1)                       
                         n                                     =                                     len                                     (arr2)                       
                         printUnion(arr1, arr2, m, n)                       
           
                         # This code is contributed by Pratik Chhajer                       

C#

                         // C# program to find union of                       
                         // two sorted arrays                       
           
                         using                                     System;                       
           
                         class                                     GFG {                       
                                                 /* Function prints union of arr1[] and arr2[]                       
                                                 m is the number of elements in arr1[]                       
                                                 n is the number of elements in arr2[] */                       
                                                 static                                     int                                     printUnion(                                     int                                     [] arr1,                       
                                                 int                                     [] arr2,                                     int                                     m,                                     int                                     n)                       
                                                 {                       
                                                 int                                     i = 0, j = 0;                       
           
                                                 while                                     (i < m && j < n) {                       
                                                 if                                     (arr1[i] < arr2[j])                       
                                                 Console.Write(arr1[i++] +                                     " "                                     );                       
                                                 else                                     if                                     (arr2[j] < arr1[i])                       
                                                 Console.Write(arr2[j++] +                                     " "                                     );                       
                                                 else                                     {                       
                                                 Console.Write(arr2[j++] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                                 }                       
           
                                                 /* Print remaining elements of                       
                                                 the larger array */                       
                                                 while                                     (i < m)                       
                                                 Console.Write(arr1[i++] +                                     " "                                     );                       
                                                 while                                     (j < n)                       
                                                 Console.Write(arr2[j++] +                                     " "                                     );                       
           
                                                 return                                     0;                       
                                                 }                       
           
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr1 = { 1, 2, 4, 5, 6 };                       
                                                 int                                     [] arr2 = { 2, 3, 5, 7 };                       
                                                 int                                     m = arr1.Length;                       
                                                 int                                     n = arr2.Length;                       
           
                                                 printUnion(arr1, arr2, m, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP program to find union of                       
                         // two sorted arrays                       
           
                         /* Function prints union of                       
                                                 arr1[] and arr2[] m is the                       
                                                 number of elements in arr1[]                       
                                                 n is the number of elements                       
                                                 in arr2[] */                       
                         function                                     printUnion(                                     $arr1                                     ,                                     $arr2                                     ,                       
                                                 $m                                     ,                                     $n                                     )                       
                         {                       
                                                 $i                                     = 0;                                     $j                                     = 0;                       
                                                 while                                     (                                     $i                                     <                                     $m                                     &&                                     $j                                     <                                     $n                                     )                       
                                                 {                       
                                                 if                                     (                                     $arr1                                     [                                     $i                                     ] <                                     $arr2                                     [                                     $j                                     ])                       
                                                 echo                                     (                                     $arr1                                     [                                     $i                                     ++] .                                     " "                                     );                       
                                   
                                                 else                                     if                                     (                                     $arr2                                     [                                     $j                                     ] <                                     $arr1                                     [                                     $i                                     ])                       
                                                 echo                                     (                                     $arr2                                     [                                     $j                                     ++] .                                     " "                                     );                       
                                   
                                                 else                       
                                                 {                       
                                                 echo                                     (                                     $arr2                                     [                                     $j                                     ++] .                                     " "                                     );                       
                                                 $i                                     ++;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Print remaining elements                       
                                                 // of the larger array                       
                                                 while                                     (                                     $i                                     <                                     $m                                     )                       
                                                 echo                                     (                                     $arr1                                     [                                     $i                                     ++] .                                     " "                                     );                       
                                   
                                                 while                                     (                                     $j                                     <                                     $n                                     )                       
                                                 echo                                     (                                     $arr2                                     [                                     $j                                     ++] .                                     " "                                     );                       
                         }                       
           
                         // Driver Code                       
                         $arr1                                     =                                     array                                     (1, 2, 4, 5, 6);                       
                         $arr2                                     =                                     array                                     (2, 3, 5, 7);                       
           
                         $m                                     = sizeof(                                     $arr1                                     );                       
                         $n                                     = sizeof(                                     $arr2                                     );                       
           
                         // Function calling                       
                         printUnion(                                     $arr1                                     ,                                     $arr2                                     ,                                     $m                                     ,                                     $n                                     );                       
           
                         // This code is contributed by Ajit.                       
                         ?>                       

Javascript

                         <script>                       
                         // JavaScript program to find union of                       
                         // two sorted arrays                       
           
                                                 /* Function prints union of arr1[] and arr2[]                       
                                                 m is the number of elements in arr1[]                       
                                                 n is the number of elements in arr2[] */                       
                                                 function                                     printUnion( arr1,  arr2,  m,  n)                       
                                                 {                       
                                                 var                                     i = 0, j = 0;                       
                                                 while                                     (i < m && j < n) {                       
                                                 if                                     (arr1[i] < arr2[j])                       
                                                 document.write(arr1[i++] +                                     " "                                     );                       
                                                 else                                     if                                     (arr2[j] < arr1[i])                       
                                                 document.write(arr2[j++] +                                     " "                                     );                       
                                                 else                                     {                       
                                                 document.write(arr2[j++] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                                 }                       
           
                                                 /* Print remaining elements of                       
                                                 the larger array */                       
                                                 while                                     (i < m)                       
                                                 document.write(arr1[i++] +                                     " "                                     );                       
                                                 while                                     (j < n)                       
                                                 document.write(arr2[j++] +                                     " "                                     );                       
           
                                                 return                                     0;                       
                                                 }                       
           
                                                 var                                     arr1 = [ 1, 2, 4, 5, 6 ];                       
                                                 var                                     arr2 = [ 2, 3, 5, 7 ];                       
                                                 var                                     m = arr1.length;                       
                                                 var                                     n = arr2.length;                       
                                                 printUnion(arr1, arr2, m, n);                       
                                   
                         // this code is contributed by shivanisinghss2110                       
                         </script>                       

输出：

1 2 3 4 5 6 7

时间复杂性： O（m+n）

处理任意阵列中的重复项： 上述代码不处理任何数组中的重复项。要处理重复项，只需检查每个元素的相邻元素是否相等。

下面是这种方法的实现。

C++

                         // C++ program for the above approach                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                                                 static                                     void                                     UnionArray(                                     int                                     arr1[],                       
                                                 int                                     arr2[],                                     int                                     l1,                                     int                                     l2)                       
                                                 {                       
                                                 // Taking max element present in either array                       
                                                 int                                     m = arr1[l1 - 1];                       
                                                 int                                     n = arr2[l2 - 1];                       
           
                                                 int                                     ans = 0;                       
           
                                                 if                                     (m > n) {                       
                                                 ans = m;                       
                                                 }                       
                                                 else                       
                                                 ans = n;                       
           
                                                 // Finding elements from 1st array                       
                                                 // (non duplicates only). Using                       
                                                 // another array for storing union                       
                                                 // elements of both arrays                       
                                                 // Assuming max element present                       
                                                 // in array is not more than 10^7                       
                                                 int                                     newtable[ans + 1];                       
                                                 memset                                     (newtable,0,                                     sizeof                                     (newtable));                       
                                                 // First element is always                       
                                                 // present in final answer                       
                                                 cout << arr1[0] <<                                     " "                                     ;                       
           
                                                 // Incrementing the First element's count                       
                                                 // in it's corresponding index in newtable                       
                                                 ++newtable[arr1[0]];                       
           
                                                 // Starting traversing the first                       
                                                 // array from 1st index till last                       
                                                 for                                     (                                     int                                     i = 1; i < l1; i++) {                       
                                                 // Checking whether current element                       
                                                 // is not equal to it's previous element                       
                                                 if                                     (arr1[i] != arr1[i - 1]) {                       
                                                 cout << arr1[i] <<                                     " "                                     ;                       
                                                 ++newtable[arr1[i]];                       
                                                 }                       
                                                 }                       
           
                                                 // Finding only non common                       
                                                 // elements from 2nd array                       
                                                 for                                     (                                     int                                     j = 0; j < l2; j++) {                       
                                                 // By checking whether it's already                       
                                                 // present in newtable or not                       
                                                 if                                     (newtable[arr2[j]] == 0) {                       
                                                 cout << arr2[j] <<                                     " "                                     ;                       
                                                 ++newtable[arr2[j]];                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr1[] = { 1, 2, 2, 2, 3 };                       
                                                 int                                     arr2[] = { 2, 3, 4, 5 };                       
                                                 int                                     n =                                     sizeof                                     (arr1) /                                     sizeof                                     (arr1[0]);                       
                                                 int                                     m =                                     sizeof                                     (arr2) /                                     sizeof                                     (arr2[0]);                       
           
                                                 UnionArray(arr1, arr2, n, m);                       
           
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by splevel62.                       

JAVA

                         // Java program to find union of two                       
                         // sorted arrays (Handling Duplicates)                       
                         class                                     FindUnion {                       
           
                                                 static                                     void                                     UnionArray(                                     int                                     arr1[],                       
                                                 int                                     arr2[])                       
                                                 {                       
                                                 // Taking max element present in either array                       
                                                 int                                     m = arr1[arr1.length -                                     1                                     ];                       
                                                 int                                     n = arr2[arr2.length -                                     1                                     ];                       
           
                                                 int                                     ans =                                     0                                     ;                       
           
                                                 if                                     (m > n) {                       
                                                 ans = m;                       
                                                 }                       
                                                 else                       
                                                 ans = n;                       
           
                                                 // Finding elements from 1st array                       
                                                 // (non duplicates only). Using                       
                                                 // another array for storing union                       
                                                 // elements of both arrays                       
                                                 // Assuming max element present                       
                                                 // in array is not more than 10^7                       
                                                 int                                     newtable[] =                                     new                                     int                                     [ans +                                     1                                     ];                       
           
                                                 // First element is always                       
                                                 // present in final answer                       
                                                 System.out.print(arr1[                                     0                                     ] +                                     " "                                     );                       
           
                                                 // Incrementing the First element's count                       
                                                 // in it's corresponding index in newtable                       
                                                 ++newtable[arr1[                                     0                                     ]];                       
           
                                                 // Starting traversing the first                       
                                                 // array from 1st index till last                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < arr1.length; i++) {                       
                                                 // Checking whether current element                       
                                                 // is not equal to it's previous element                       
                                                 if                                     (arr1[i] != arr1[i -                                     1                                     ]) {                       
                                                 System.out.print(arr1[i] +                                     " "                                     );                       
                                                 ++newtable[arr1[i]];                       
                                                 }                       
                                                 }                       
           
                                                 // Finding only non common                       
                                                 // elements from 2nd array                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < arr2.length; j++) {                       
                                                 // By checking whether it's already                       
                                                 // present in newtable or not                       
                                                 if                                     (newtable[arr2[j]] ==                                     0                                     ) {                       
                                                 System.out.print(arr2[j] +                                     " "                                     );                       
                                                 ++newtable[arr2[j]];                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     arr1[] = {                                     1                                     ,                                     2                                     ,                                     2                                     ,                                     2                                     ,                                     3                                     };                       
                                                 int                                     arr2[] = {                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     };                       
           
                                                 UnionArray(arr1, arr2);                       
                                                 }                       
                         }                       

蟒蛇3

                         # Python3 program to find union of two                       
                         # sorted arrays (Handling Duplicates)                       
                         def                                     union_array(arr1, arr2):                       
                                                 m                                     =                                     len                                     (arr1)                       
                                                 n                                     =                                     len                                     (arr2)                       
                                                 i                                     =                                     0                       
                                                 j                                     =                                     0                       
                                   
                                                 # keep track of last element to avoid duplicates                       
                                                 prev                                     =                                     None                       
                                   
                                                 while                                     i < m                                     and                                     j < n:                       
                                                 if                                     arr1[i] < arr2[j]:                       
                                                 if                                     arr1[i] !                                     =                                     prev:                       
                                                 print                                     (arr1[i], end                                     =                                     ' '                                     )                       
                                                 prev                                     =                                     arr1[i]                       
                                                 i                                     +                                     =                                     1                       
                                                 elif                                     arr1[i] > arr2[j]:                       
                                                 if                                     arr2[j] !                                     =                                     prev:                       
                                                 print                                     (arr2[j], end                                     =                                     ' '                                     )                       
                                                 prev                                     =                                     arr2[j]                       
                                                 j                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 if                                     arr1[i] !                                     =                                     prev:                       
                                                 print                                     (arr1[i], end                                     =                                     ' '                                     )                       
                                                 prev                                     =                                     arr1[i]                       
                                                 i                                     +                                     =                                     1                       
                                                 j                                     +                                     =                                     1                       
                                   
                                                 while                                     i < m:                       
                                                 if                                     arr1[i] !                                     =                                     prev:                       
                                                 print                                     (arr1[i], end                                     =                                     ' '                                     )                       
                                                 prev                                     =                                     arr1[i]                       
                                                 i                                     +                                     =                                     1                       
           
                                                 while                                     j < n:                       
                                                 if                                     arr2[j] !                                     =                                     prev:                       
                                                 print                                     (arr2[j], end                                     =                                     ' '                                     )                       
                                                 prev                                     =                                     arr2[j]                       
                                                 j                                     +                                     =                                     1                       
                                   
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 arr1                                     =                                     [                                     1                                     ,                                     2                                     ,                                     2                                     ,                                     2                                     ,                                     3                                     ]                       
                                                 arr2                                     =                                     [                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ]                       
                                   
                                                 union_array(arr1, arr2)                       
           
                         # This code is contributed by Sanjay Kumar                       

C#

                         // C# program to find union of two                       
                         // sorted arrays (Handling Duplicates)                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 static                                     void                                     UnionArray(                                     int                                     [] arr1,                       
                                                 int                                     [] arr2)                       
                                                 {                       
           
                                                 // Taking max element present                       
                                                 // in either array                       
                                                 int                                     m = arr1[arr1.Length - 1];                       
                                                 int                                     n = arr2[arr2.Length - 1];                       
           
                                                 int                                     ans = 0;                       
           
                                                 if                                     (m > n)                       
                                                 ans = m;                       
                                                 else                       
                                                 ans = n;                       
           
                                                 // Finding elements from 1st array                       
                                                 // (non duplicates only). Using                       
                                                 // another array for storing union                       
                                                 // elements of both arrays                       
                                                 // Assuming max element present                       
                                                 // in array is not more than 10^7                       
                                                 int                                     [] newtable =                                     new                                     int                                     [ans + 1];                       
           
                                                 // First element is always                       
                                                 // present in final answer                       
                                                 Console.Write(arr1[0] +                                     " "                                     );                       
           
                                                 // Incrementing the First element's                       
                                                 // count in it's corresponding                       
                                                 // index in newtable                       
                                                 ++newtable[arr1[0]];                       
           
                                                 // Starting traversing the first                       
                                                 // array from 1st index till last                       
                                                 for                                     (                                     int                                     i = 1; i < arr1.Length; i++) {                       
                                                 // Checking whether current                       
                                                 // element is not equal to                       
                                                 // it's previous element                       
                                                 if                                     (arr1[i] != arr1[i - 1]) {                       
                                                 Console.Write(arr1[i] +                                     " "                                     );                       
                                                 ++newtable[arr1[i]];                       
                                                 }                       
                                                 }                       
           
                                                 // Finding only non common                       
                                                 // elements from 2nd array                       
                                                 for                                     (                                     int                                     j = 0; j < arr2.Length; j++) {                       
                                                 // By checking whether it's already                       
                                                 // present in newtable or not                       
                                                 if                                     (newtable[arr2[j]] == 0) {                       
                                                 Console.Write(arr2[j] +                                     " "                                     );                       
                                                 ++newtable[arr2[j]];                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr1 = { 1, 2, 2, 2, 3 };                       
                                                 int                                     [] arr2 = { 2, 3, 4, 5 };                       
           
                                                 UnionArray(arr1, arr2);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

Javascript

                         <script>                       
                         // javascript program to find union of two                       
                         // sorted arrays (Handling Duplicates)                       
           
                                                 function                                     UnionArray(arr1 , arr2) {                       
                                                 // Taking max element present in either array                       
                                                 var                                     m = arr1[arr1.length - 1];                       
                                                 var                                     n = arr2[arr2.length - 1];                       
           
                                                 var                                     ans = 0;                       
           
                                                 if                                     (m > n) {                       
                                                 ans = m;                       
                                                 }                                     else                       
                                                 ans = n;                       
           
                                                 // Finding elements from 1st array                       
                                                 // (non duplicates only). Using                       
                                                 // another array for storing union                       
                                                 // elements of both arrays                       
                                                 // Assuming max element present                       
                                                 // in array is not more than 10^7                       
                                                 var                                     newtable = Array(ans+1).fill(0);                       
           
                                                 // First element is always                       
                                                 // present in final answer                       
                                                 document.write(arr1[0] +                                     " "                                     );                       
           
                                                 // Incrementing the First element's count                       
                                                 // in it's corresponding index in newtable                       
                                                 newtable[arr1[0]]+=1;                       
           
                                                 // Starting traversing the first                       
                                                 // array from 1st index till last                       
                                                 for                                     (                                     var                                     i = 1; i < arr1.length; i++) {                       
                                                 // Checking whether current element                       
                                                 // is not equal to it's previous element                       
                                                 if                                     (arr1[i] != arr1[i - 1]) {                       
                                                 document.write(arr1[i] +                                     " "                                     );                       
                                                 newtable[arr1[i]]+= 1;                       
                                                 }                       
                                                 }                       
           
                                                 // Finding only non common                       
                                                 // elements from 2nd array                       
                                                 for                                     (                                     var                                     j = 0; j < arr2.length; j++) {                       
                                                 // By checking whether it's already                       
                                                 // present in newtable or not                       
                                                 if                                     (newtable[arr2[j]] == 0) {                       
                                                 document.write(arr2[j] +                                     " "                                     );                       
                                                 ++newtable[arr2[j]];                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 var                                     arr1 = [ 1, 2, 2, 2, 3 ];                       
                                                 var                                     arr2 = [ 2, 3, 4, 5 ];                       
           
                                                 UnionArray(arr1, arr2);                       
           
                         // This code is contributed by gauravrajput1                       
                         </script>                       

输出

1 2 3

幸亏 桑杰·库马尔 感谢你提出这个解决方案。

数组arr1[]和arr2[]的交集

要查找两个排序数组的交集，请遵循以下方法：

1）使用两个索引变量i和j，初始值i=0，j=0 2）如果arr1[i]小于arr2[j]，则增量i。 3）如果arr1[i]大于arr2[j]，则增加j。 4）如果两者相同，则打印其中任何一个并增加i和j。

以下是上述方法的实施情况：

C++

                         // C++ program to find intersection of                       
                         // two sorted arrays                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         /* Function prints Intersection of arr1[] and arr2[]                       
                         m is the number of elements in arr1[]                       
                         n is the number of elements in arr2[] */                       
                         void                                     printIntersection(                                     int                                     arr1[],                                     int                                     arr2[],                                     int                                     m,                                     int                                     n)                       
                         {                       
                                                 int                                     i = 0, j = 0;                       
                                                 while                                     (i < m && j < n) {                       
                                                 if                                     (arr1[i] < arr2[j])                       
                                                 i++;                       
                                                 else                                     if                                     (arr2[j] < arr1[i])                       
                                                 j++;                       
                                                 else                                     /* if arr1[i] == arr2[j] */                       
                                                 {                       
                                                 cout << arr2[j] <<                                     " "                                     ;                       
                                                 i++;                       
                                                 j++;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         /* Driver program to test above function */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr1[] = { 1, 2, 4, 5, 6 };                       
                                                 int                                     arr2[] = { 2, 3, 5, 7 };                       
           
                                                 int                                     m =                                     sizeof                                     (arr1) /                                     sizeof                                     (arr1[0]);                       
                                                 int                                     n =                                     sizeof                                     (arr2) /                                     sizeof                                     (arr2[0]);                       
           
                                                 // Function calling                       
                                                 printIntersection(arr1, arr2, m, n);                       
           
                                                 return                                     0;                       
                         }                       

C

                         // C program to find intersection of                       
                         // two sorted arrays                       
                         #include <stdio.h>                       
           
                         /* Function prints Intersection of arr1[] and arr2[]                       
                                                 m is the number of elements in arr1[]                       
                                                 n is the number of elements in arr2[] */                       
                         void                                     printIntersection(                                     int                                     arr1[],                                     int                                     arr2[],                                     int                                     m,                                     int                                     n)                       
                         {                       
                                                 int                                     i = 0, j = 0;                       
                                                 while                                     (i < m && j < n) {                       
                                                 if                                     (arr1[i] < arr2[j])                       
                                                 i++;                       
                                                 else                                     if                                     (arr2[j] < arr1[i])                       
                                                 j++;                       
                                                 else                                     /* if arr1[i] == arr2[j] */                       
                                                 {                       
                                                 printf                                     (                                     " %d "                                     , arr2[j++]);                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         /* Driver program to test above function */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr1[] = { 1, 2, 4, 5, 6 };                       
                                                 int                                     arr2[] = { 2, 3, 5, 7 };                       
                                                 int                                     m =                                     sizeof                                     (arr1) /                                     sizeof                                     (arr1[0]);                       
                                                 int                                     n =                                     sizeof                                     (arr2) /                                     sizeof                                     (arr2[0]);                       
                                                 printIntersection(arr1, arr2, m, n);                       
                                                 getchar                                     ();                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find intersection of                       
                         // two sorted arrays                       
           
                         class                                     FindIntersection {                       
                                                 /* Function prints Intersection of arr1[] and arr2[]                       
                                                 m is the number of elements in arr1[]                       
                                                 n is the number of elements in arr2[] */                       
                                                 static                                     void                                     printIntersection(                                     int                                     arr1[],                                     int                                     arr2[],                                     int                                     m,                                     int                                     n)                       
                                                 {                       
                                                 int                                     i =                                     0                                     , j =                                     0                                     ;                       
                                                 while                                     (i < m && j < n) {                       
                                                 if                                     (arr1[i] < arr2[j])                       
                                                 i++;                       
                                                 else                                     if                                     (arr2[j] < arr1[i])                       
                                                 j++;                       
                                                 else                                     {                       
                                                 System.out.print(arr2[j++] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     arr1[] = {                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     };                       
                                                 int                                     arr2[] = {                                     2                                     ,                                     3                                     ,                                     5                                     ,                                     7                                     };                       
                                                 int                                     m = arr1.length;                       
                                                 int                                     n = arr2.length;                       
                                                 printIntersection(arr1, arr2, m, n);                       
                                                 }                       
                         }                       

蟒蛇3

                         # Python program to find intersection of                       
                         # two sorted arrays                       
                         # Function prints Intersection of arr1[] and arr2[]                       
                         # m is the number of elements in arr1[]                       
                         # n is the number of elements in arr2[]                       
                         def                                     printIntersection(arr1, arr2, m, n):                       
                                                 i, j                                     =                                     0                                     ,                                     0                       
                                                 while                                     i < m                                     and                                     j < n:                       
                                                 if                                     arr1[i] < arr2[j]:                       
                                                 i                                     +                                     =                                     1                       
                                                 elif                                     arr2[j] < arr1[i]:                       
                                                 j                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 print                                     (arr2[j],end                                     =                                     " "                                     )                       
                                                 j                                     +                                     =                                     1                       
                                                 i                                     +                                     =                                     1                       
           
                         # Driver program to test above function                       
                         arr1                                     =                                     [                                     1                                     ,                                     2                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ]                       
                         arr2                                     =                                     [                                     2                                     ,                                     3                                     ,                                     5                                     ,                                     7                                     ]                       
                         m                                     =                                     len                                     (arr1)                       
                         n                                     =                                     len                                     (arr2)                       
                         printIntersection(arr1, arr2, m, n)                       
           
                         # This code is contributed by Pratik Chhajer                       

C#

                         // C# program to find Intersection of                       
                         // two sorted arrays                       
           
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 /* Function prints Intersection of arr1[]                       
                                                 and arr2[] m is the number of elements in arr1[]                       
                                                 n is the number of elements in arr2[] */                       
                                                 static                                     void                                     printIntersection(                                     int                                     [] arr1,                       
                                                 int                                     [] arr2,                                     int                                     m,                                     int                                     n)                       
                                                 {                       
                                                 int                                     i = 0, j = 0;                       
           
                                                 while                                     (i < m && j < n) {                       
                                                 if                                     (arr1[i] < arr2[j])                       
                                                 i++;                       
                                                 else                                     if                                     (arr2[j] < arr1[i])                       
                                                 j++;                       
                                                 else                                     {                       
                                                 Console.Write(arr2[j++] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr1 = { 1, 2, 4, 5, 6 };                       
                                                 int                                     [] arr2 = { 2, 3, 5, 7 };                       
                                                 int                                     m = arr1.Length;                       
                                                 int                                     n = arr2.Length;                       
           
                                                 printIntersection(arr1, arr2, m, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP program to find intersection of                       
                         // two sorted arrays                       
           
                         /* Function prints Intersection                       
                                                 of arr1[] and arr2[] m is the                       
                                                 number of elements in arr1[]                       
                                                 n is the number of elements                       
                                                 in arr2[] */                       
                         function                                     printIntersection(                                     $arr1                                     ,                                     $arr2                                     ,                       
                                                 $m                                     ,                                     $n                                     )                       
                         {                       
                                                 $i                                     = 0 ;                       
                                                 $j                                     = 0;                       
                                                 while                                     (                                     $i                                     <                                     $m                                     &&                                     $j                                     <                                     $n                                     )                       
                                                 {                       
                                                 if                                     (                                     $arr1                                     [                                     $i                                     ] <                                     $arr2                                     [                                     $j                                     ])                       
                                                 $i                                     ++;                       
                                                 else                                     if                                     (                                     $arr2                                     [                                     $j                                     ] <                                     $arr1                                     [                                     $i                                     ])                       
                                                 $j                                     ++;                       
                                   
                                                 /* if arr1[i] == arr2[j] */                       
                                                 else                       
                                                 {                       
                                                 echo                                     $arr2                                     [                                     $j                                     ],                                     " "                                     ;                       
                                                 $i                                     ++;                       
                                                 $j                                     ++;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         $arr1                                     =                                     array                                     (1, 2, 4, 5, 6);                       
                         $arr2                                     =                                     array                                     (2, 3, 5, 7);                       
           
                         $m                                     =                                     count                                     (                                     $arr1                                     );                       
                         $n                                     =                                     count                                     (                                     $arr2                                     );                       
           
                         // Function calling                       
                         printIntersection(                                     $arr1                                     ,                                     $arr2                                     ,                                     $m                                     ,                                     $n                                     );                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find intersection of                       
                         // two sorted arrays                       
           
                         // Function prints Intersection of arr1[] and arr2[]                       
                         // m is the number of elements in arr1[]                       
                         // n is the number of elements in arr2[]                       
                         function                                     printIntersection(arr1, arr2, m, n)                       
                         {                       
                                                 var                                     i = 0, j = 0;                       
                                                 while                                     (i < m && j < n)                       
                                                 {                       
                                                 if                                     (arr1[i] < arr2[j])                       
                                                 i++;                       
                                                 else                                     if                                     (arr2[j] < arr1[i])                       
                                                 j++;                       
                                                 else                       
                                                 {                       
                                                 document.write(arr2[j++] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         var                                     arr1 = [ 1, 2, 4, 5, 6 ];                       
                         var                                     arr2 = [ 2, 3, 5, 7 ];                       
           
                         var                                     m = arr1.length;                       
                         var                                     n = arr2.length;                       
           
                         printIntersection(arr1, arr2, m, n);                       
           
                         // This code is contributed by shivanisinghss2110                       
           
                         </script>                       

输出：

2 5

时间复杂性： O（m+n）

处理重复阵列： 上述代码不处理数组中的重复元素。交叉点不应计算重复元素。要处理重复项，只需检查当前元素是否已存在于交叉点列表中。下面是这种方法的实现。

蟒蛇3

                         # Python3 program to find Intersection of two                       
                         # Sorted Arrays (Handling Duplicates)                       
                         def                                     IntersectionArray(a, b, n, m):                       
                                                 '''                       
                                                 :param a: given sorted array a                       
                                                 :param n: size of sorted array a                       
                                                 :param b: given sorted array b                       
                                                 :param m: size of sorted array b                       
                                                 :return: array of intersection of two array or -1                       
                                                 '''                       
           
                                                 Intersection                                     =                                     []                       
                                                 i                                     =                                     j                                     =                                     0                       
                                   
                                                 while                                     i < n                                     and                                     j < m:                       
                                                 if                                     a[i]                                     =                                     =                                     b[j]:                       
           
                                                 # If duplicate already present in Intersection list                       
                                                 if                                     len                                     (Intersection) >                                     0                                     and                                     Intersection[                                     -                                     1                                     ]                                     =                                     =                                     a[i]:                       
                                                 i                                     +                                     =                                     1                       
                                                 j                                     +                                     =                                     1                       
           
                                                 # If no duplicate is present in Intersection list                       
                                                 else                                     :                       
                                                 Intersection.append(a[i])                       
                                                 i                                     +                                     =                                     1                       
                                                 j                                     +                                     =                                     1                       
                                                 elif                                     a[i] < b[j]:                       
                                                 i                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 j                                     +                                     =                                     1                       
                                   
                                                 if                                     not                                     len                                     (Intersection):                       
                                                 return                                     [                                     -                                     1                                     ]                       
                                                 return                                     Intersection                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 arr1                                     =                                     [                                     1                                     ,                                     2                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ]                       
                                                 arr2                                     =                                     [                                     2                                     ,                                     2                                     ,                                     4                                     ,                                     6                                     ,                                     7                                     ,                                     8                                     ]                       
                                   
                                                 l                                     =                                     IntersectionArray(arr1, arr2,                                     len                                     (arr1),                                     len                                     (arr2))                       
                                                 print                                     (                                     *                                     l)                       
           
                         # This code is contributed by Abhishek Kumar                       

输出：

2 4

时间复杂性： O（m+n） 辅助空间： O（最小（m，n））

当两个给定数组的大小差异很大时，另一种方法很有用。 其思想是遍历较短的数组，并在大数组中对短数组的每个元素进行二进制搜索（注意数组是排序的）。该解的时间复杂度为O（min（mLogn，nLogm））。当较大长度与较小长度之比大于对数阶时，该解决方案比上述方法效果更好。

有关未排序的数组，请参见下面的帖子。求两个未排序数组的并集和交集如果您在上述代码/算法中发现任何错误，请写下评论，或者寻找其他方法来解决相同的问题。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章