两排序数组的对称差分-yiteyi-C++库

有两个排序数组啊和啊2 .我们必须找到 对称差分 关于Aarr1和arr2。对称差分基本上包含两个数组的所有元素，公共元素除外。

null

Symmetric difference of two array is the all array elements of both array except the elements that are presents in both array.SymmDiff = (arr1 - arr2) UNION (arr2 - arr1).                ORSymmDiff = (arr1 UNION arr2) - (arr1 INTERSECTION arr2).

例如：

Input : arr1[] = {2, 4, 5, 7, 8, 10, 12, 15}.        arr2[] = {5, 8, 11, 12, 14, 15}.Output : 2 4 7 10 11 14                arr1[] - arr2[] = {2, 4, 7, 10}.        arr[2] - arr1[] = {11, 14}.        SymmDiff = (arr1[] - arr2[]) UNION                    (arr2[] - arr1[]).                 = {2, 4, 7, 10, 11, 14}.Input : arr1[] = {1, 3, 5, 8, 15, 27, 35}.        arr2[] = {5, 7, 8, 11, 15, 18, 35}.Output : 1 3 7 11 18 27        arr1[] - arr2[] = {1, 3, 27}.        arr[2] - arr1[] = {7, 11, 18}.        SymmDiff = (arr1[] - arr2[]) UNION                    (arr2[] - arr1[]).                 = {1, 3, 7, 11, 18, 27}.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 简单解决方案 就是逐个遍历两个数组。对于一个数组的每个元素，检查它是否存在于其他数组中。如果是，则忽略它，否则打印它。此解决方案的时间复杂度为O（n*n）一 有效解决方案 寻找两个排序数组的对称差类似于合并排序的合并过程 .如果当前两个元素不匹配，我们同时遍历两个数组并打印较小的元素，然后在具有较小元素的数组中前进。否则我们忽略元素，在两个数组中继续前进。

C++

                         // C++ program to find the symmetric difference                       
                         // of two sorted array.                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
                         void                                     symmDiff(                                     int                                     arr1[],                                     int                                     arr2[],                                     int                                     n,                                     int                                     m)                       
                         {                       
                                                 // Traverse both arrays simultaneously.                       
                                                 int                                     i = 0, j = 0;                       
                                                 while                                     (i < n && j < m) {                       
                                   
                                                 // Print smaller element and move                       
                                                 // ahead in array with smaller element                       
                                                 if                                     (arr1[i] < arr2[j]) {                       
                                                 cout << arr1[i] <<                                     " "                                     ;                       
                                                 i++;                       
                                                 }                       
                                                 else                                     if                                     (arr2[j] < arr1[i]) {                       
                                                 cout << arr2[j] <<                                     " "                                     ;                       
                                                 j++;                       
                                                 }                       
           
                                                 // If both elements same, move ahead                       
                                                 // in both arrays.                       
                                                 else                                     {                       
                                                 i++;                       
                                                 j++;                       
                                                 }                       
                                                 }                       
                                                 while                                     (i < n) {                       
                                                 cout << arr1[i] <<                                     " "                                     ;                       
                                                 i++;                       
                                                 }                       
                                                 while                                     (j < m) {                       
                                                 cout << arr2[j] <<                                     " "                                     ;                       
                                                 j++;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr1[] = { 2, 4, 5, 7, 8, 10, 12, 15 };                       
                                                 int                                     arr2[] = { 5, 8, 11, 12, 14, 15 };                       
                                                 int                                     n =                                     sizeof                                     (arr1) /                                     sizeof                                     (arr1[0]);                       
                                                 int                                     m =                                     sizeof                                     (arr2) /                                     sizeof                                     (arr2[0]);                       
                                                 symmDiff(arr1, arr2, n, m);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find the symmetric                       
                         // difference of two sorted array.                       
                         import                                     java.util.*;                       
                         class                                     GFG {                       
                                                 static                                     void                                     symmDiff(                                     int                                     [] arr1,                                     int                                     [] arr2,                                     int                                     n,                       
                                                 int                                     m)                       
                                                 {                       
                                                 // Traverse both arrays simultaneously.                       
                                                 int                                     i =                                     0                                     , j =                                     0                                     ;                       
                                                 while                                     (i < n && j < m) {                       
                                                 // Print smaller element and move                       
                                                 // ahead in array with smaller element                       
                                                 if                                     (arr1[i] < arr2[j]) {                       
                                                 System.out.print(arr1[i] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                                 else                                     if                                     (arr2[j] < arr1[i]) {                       
                                                 System.out.print(arr2[j] +                                     " "                                     );                       
                                                 j++;                       
                                                 }                       
           
                                                 // If both elements same, move ahead                       
                                                 // in both arrays.                       
                                                 else                                     {                       
                                                 i++;                       
                                                 j++;                       
                                                 }                       
                                                 }                       
                                                 while                                     (i < n) {                       
                                                 System.out.print(arr1[i] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                                 while                                     (j < m) {                       
                                                 System.out.print(arr2[j] +                                     " "                                     );                       
                                                 j++;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     [] arr1 = {                                     2                                     ,                                     4                                     ,                                     5                                     ,                                     7                                     ,                                     8                                     ,                                     10                                     ,                                     12                                     ,                                     15                                     };                       
                                                 int                                     [] arr2 = {                                     5                                     ,                                     8                                     ,                                     11                                     ,                                     12                                     ,                                     14                                     ,                                     15                                     };                       
                                                 int                                     n = arr1.length;                       
                                                 int                                     m = arr2.length;                       
                                                 symmDiff(arr1, arr2, n, m);                       
                                                 }                       
                         }                       
                         /* This code is contributed by Kriti Shukla */                       

Python3

                         # Python3 program to                       
                         # find the symmetric                       
                         # difference of two                       
                         # sorted array.                       
           
           
                         def                                     symmDiff(arr1, arr2, n, m):                       
           
                                                 # Traverse both arrays                       
                                                 # simultaneously.                       
                                                 i                                     =                                     0                       
                                                 j                                     =                                     0                       
                                                 while                                     (i < n                                     and                                     j < m):                       
           
                                                 # Print smaller element                       
                                                 # and move ahead in                       
                                                 # array with smaller                       
                                                 # element                       
                                                 if                                     (arr1[i] < arr2[j]):                       
                                                 print                                     (arr1[i], end                                     =                                     " "                                     )                       
                                                 i                                     +                                     =                                     1                       
           
                                                 elif                                     (arr2[j] < arr1[i]):                       
                                                 print                                     (arr2[j], end                                     =                                     " "                                     )                       
                                                 j                                     +                                     =                                     1                       
           
                                                 # If both elements                       
                                                 # same, move ahead                       
                                                 # in both arrays.                       
                                                 else                                     :                       
           
                                                 i                                     +                                     =                                     1                       
                                                 j                                     +                                     =                                     1                       
           
                                                 while                                     i < n:                       
                                                 print                                     (arr1[i], end                                     =                                     ' '                                     )                       
                                                 i                                     +                                     =                                     1                       
           
                                                 while                                     j < m:                       
                                                 print                                     (arr2[j], end                                     =                                     ' '                                     )                       
                                                 j                                     +                                     =                                     1                       
           
           
                         # Driver code                       
                         arr1                                     =                                     [                                     2                                     ,                                     4                                     ,                                     5                                     ,                                     7                                     ,                                     8                                     ,                                     10                                     ,                                     12                                     ,                                     15                                     ]                       
                         arr2                                     =                                     [                                     5                                     ,                                     8                                     ,                                     11                                     ,                                     12                                     ,                                     14                                     ,                                     15                                     ]                       
                         n                                     =                                     len                                     (arr1)                       
                         m                                     =                                     len                                     (arr2)                       
           
                         symmDiff(arr1, arr2, n, m)                       
           
                         # This code is contributed by Smitha Dinesh Semwal                       

C#

                         // C# program to find the symmetric                       
                         // difference of two sorted array.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 static                                     void                                     symmDiff(                                     int                                     [] arr1,                                     int                                     [] arr2,                                     int                                     n,                       
                                                 int                                     m)                       
                                                 {                       
           
                                                 // Traverse both arrays simultaneously.                       
                                                 int                                     i = 0, j = 0;                       
           
                                                 while                                     (i < n && j < m) {                       
           
                                                 // Print smaller element and move                       
                                                 // ahead in array with smaller element                       
                                                 if                                     (arr1[i] < arr2[j]) {                       
                                                 Console.Write(arr1[i] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                                 else                                     if                                     (arr2[j] < arr1[i]) {                       
                                                 Console.Write(arr2[j] +                                     " "                                     );                       
                                                 j++;                       
                                                 }                       
           
                                                 // If both elements same, move ahead                       
                                                 // in both arrays.                       
                                                 else                                     {                       
                                                 i++;                       
                                                 j++;                       
                                                 }                       
                                                 }                       
                                                 while                                     (i < n) {                       
                                                 Console.Write(arr1[i] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
           
                                                 while                                     (j < m) {                       
                                                 Console.Write(arr2[j] +                                     " "                                     );                       
                                                 j++;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr1 = { 2, 4, 5, 7, 8, 10, 12, 15 };                       
                                                 int                                     [] arr2 = { 5, 8, 11, 12, 14, 15 };                       
                                                 int                                     n = arr1.Length;                       
                                                 int                                     m = arr2.Length;                       
           
                                                 symmDiff(arr1, arr2, n, m);                       
                                                 }                       
                         }                       
           
                         /* This code is contributed by vt_m*/                       

PHP

                         <?php                       
                         // PHP program to find the                       
                         // symmetric difference                       
                         // of two sorted array.                       
                         function                                     symmDiff(                                     $arr1                                     ,                                     $arr2                                     ,                       
                                                 $n                                     ,                                     $m                                     )                       
                         {                       
                                   
                                                 // Traverse both arrays                       
                                                 // simultaneously.                       
                                                 $i                                     = 0;                                     $j                                     = 0;                       
                                                 while                                     (                                     $i                                     <                                     $n                                     &&                                     $j                                     <                                     $m                                     )                       
                                                 {                       
                                   
                                                 // Print smaller element                       
                                                 // and move ahead in array                       
                                                 // with smaller element                       
                                                 if                                     (                                     $arr1                                     [                                     $i                                     ] <                                     $arr2                                     [                                     $j                                     ])                       
                                                 {                       
                                                 echo                                     (                                     $arr1                                     [                                     $i                                     ] .                                     " "                                     );                       
                                                 $i                                     ++;                       
                                                 }                       
                                                 else                                     if                                     (                                     $arr2                                     [                                     $j                                     ] <                                     $arr1                                     [                                     $i                                     ])                       
                                                 {                       
                                                 echo                                     (                                     $arr2                                     [                                     $j                                     ] .                                     " "                                     );                       
                                                 $j                                     ++;                       
                                                 }                       
           
                                                 // If both elements same,                       
                                                 // move ahead in both arrays                       
                                                 else                       
                                                 {                       
                                                 $i                                     ++;                       
                                                 $j                                     ++;                       
                                                 }                       
                                                 }                       
                                   
                                                 while                                     (                                     $i                                     <                                     $n                                     ) {                       
                                                 echo                                     (                                     $arr1                                     [                                     $i                                     ] .                                     " "                                     );                       
                                                 $i                                     ++;                       
                                                 }                       
           
                                                 while                                     (                                     $j                                     <                                     $m                                     ) {                       
                                                 echo                                     (                                     $arr2                                     [                                     $j                                     ] .                                     " "                                     );                       
                                                 $j                                     ++;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         $arr1                                     =                                     array                                     (2, 4, 5, 7, 8, 10, 12, 15);                       
                         $arr2                                     =                                     array                                     (5, 8, 11, 12, 14, 15);                       
                         $n                                     = sizeof(                                     $arr1                                     );                       
                         $m                                     = sizeof(                                     $arr2                                     );                       
                         symmDiff(                                     $arr1                                     ,                                     $arr2                                     ,                                     $n                                     ,                                     $m                                     );                       
           
                         // This code is contributed by Ajit.                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // Javascript program to find the symmetric                       
                                                 // difference of two sorted array.                       
                                   
                                                 function                                     symmDiff(arr1, arr2, n, m)                       
                                                 {                       
                                   
                                                 // Traverse both arrays simultaneously.                       
                                                 let i = 0, j = 0;                       
                                   
                                                 while                                     (i < n && j < m) {                       
                                   
                                                 // Print smaller element and move                       
                                                 // ahead in array with smaller element                       
                                                 if                                     (arr1[i] < arr2[j]) {                       
                                                 document.write(arr1[i] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                                 else                                     if                                     (arr2[j] < arr1[i]) {                       
                                                 document.write(arr2[j] +                                     " "                                     );                       
                                                 j++;                       
                                                 }                       
                                   
                                                 // If both elements same, move ahead                       
                                                 // in both arrays.                       
                                                 else                                     {                       
                                                 i++;                       
                                                 j++;                       
                                                 }                       
                                                 }                       
                                                 while                                     (i < n) {                       
                                                 document.write(arr1[i] +                                     " "                                     );                       
                                                 i++;                       
                                                 }                       
                                   
                                                 while                                     (j < m) {                       
                                                 document.write(arr2[j] +                                     " "                                     );                       
                                                 j++;                       
                                                 }                       
                                                 }                       
                                   
                                                 let arr1 = [ 2, 4, 5, 7, 8, 10, 12, 15 ];                       
                                                 let arr2 = [ 5, 8, 11, 12, 14, 15 ];                       
                                                 let n = arr1.length;                       
                                                 let m = arr2.length;                       
           
                                                 symmDiff(arr1, arr2, n, m);                       
                                   
                         </script>                       

输出：

2 4 7 10 11 14

时间复杂性： O（m+n）。本文由 达曼德拉·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章