在另一个被洗牌的数组中查找缺失的数字-yiteyi-C++库

给定一个由n个正整数组成的数组“arr1”。arr1[]的内容被复制到另一个数组“arr2”，但数字被洗牌，一个元素被删除。找到缺失的元素（不使用任何额外的空间，时间复杂度为O（n））。 例如：

null

Input : arr1[] = {4, 8, 1, 3, 7},         arr2[] = {7, 4, 3, 1}Output : 8Input : arr1[] = {12, 10, 15, 23, 11, 30},         arr2[] = {15, 12, 23, 11, 30}Output : 10

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 一个一个地考虑第一个数组的每个元素和第二个数组中的搜索。一旦我们找到丢失的元素，我们就会返回。该解的时间复杂度为O（n） ^2. ) 一 有效解决方案 基于XOR。每个元素的组合出现次数为两次，一次出现在“arr1”中，另一次出现在“arr2”中，除了一个元素在“arr1”中只有一次出现。我们知道（a或a）=0。所以，简单地对两个数组的元素进行异或运算。结果将是丢失的号码。

C++

                         // C++ implementation to find the                       
                         // missing number in shuffled array                       
                         // C++ implementation to find the                       
                         // missing number in shuffled array                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns the missing number                       
                         // Size of arr2[] is n-1                       
                         int                                     missingNumber(                                     int                                     arr1[],                                     int                                     arr2[],                       
                                                 int                                     n)                       
                         {                       
                                                 // Missing number 'mnum'                       
                                                 int                                     mnum = 0;                       
           
                                                 // 1st array is of size 'n'                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 mnum = mnum ^ arr1[i];                       
           
                                                 // 2nd array is of size 'n - 1'                       
                                                 for                                     (                                     int                                     i = 0; i < n - 1; i++)                       
                                                 mnum = mnum ^ arr2[i];                       
           
                                                 // Required missing number                       
                                                 return                                     mnum;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr1[] = {4, 8, 1, 3, 7};                       
                                                 int                                     arr2[] = {7, 4, 3, 1};                       
                                                 int                                     n =                                     sizeof                                     (arr1) /                                     sizeof                                     (arr1[0]);                       
                                                 cout <<                                     "Missing number = "                       
                                                 << missingNumber(arr1, arr2, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to find the                       
                         // missing number in shuffled array                       
           
                         class                                     GFG                       
                         {                       
                                                 // Returns the missing number                       
                                                 // Size of arr2[] is n-1                       
                                                 static                                     int                                     missingNumber(                                     int                                     arr1[],                       
                                                 int                                     arr2[],                       
                                                 int                                     n)                       
                                                 {                       
                                                 // Missing number 'mnum'                       
                                                 int                                     mnum =                                     0                                     ;                       
                                   
                                                 // 1st array is of size 'n'                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 mnum = mnum ^ arr1[i];                       
                                   
                                                 // 2nd array is of size 'n - 1'                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n -                                     1                                     ; i++)                       
                                                 mnum = mnum ^ arr2[i];                       
                                   
                                                 // Required missing number                       
                                                 return                                     mnum;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr1[] = {                                     4                                     ,                                     8                                     ,                                     1                                     ,                                     3                                     ,                                     7                                     };                       
                                                 int                                     arr2[] = {                                     7                                     ,                                     4                                     ,                                     3                                     ,                                     1                                     };                       
                                                 int                                     n = arr1.length;                       
                                   
                                                 System.out.println(                                     "Missing number = "                       
                                                 + missingNumber(arr1, arr2, n));                       
                                                 }                       
                         }                       

Python3

                         # Python3 implementation to find the                       
                         # missing number in shuffled array                       
           
                         # Returns the missing number                       
                         # Size of arr2[] is n - 1                       
                         def                                     missingNumber(arr1, arr2, n):                       
           
                                                 # missing number 'mnum'                       
                                                 mnum                                     =                                     0                       
           
                                                 # 1st array is of size 'n'                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 mnum                                     =                                     mnum ^ arr1[i]                       
           
                                                 # 2nd array is of size 'n - 1'                       
                                                 for                                     i                                     in                                     range                                     (n                                     -                                     1                                     ):                       
                                                 mnum                                     =                                     mnum ^ arr2[i]                       
           
                                                 # Required missing number                       
                                                 return                                     mnum                       
           
                         # Driver Code                       
                         arr1                                     =                                     [                                     4                                     ,                                     8                                     ,                                     1                                     ,                                     3                                     ,                                     7                                     ]                       
                         arr2                                     =                                     [                                     7                                     ,                                     4                                     ,                                     3                                     ,                                     1                                     ]                       
                         n                                     =                                     len                                     (arr1)                       
                         print                                     (                                     "Missing number = "                                     ,                       
                                                 missingNumber(arr1, arr2, n))                       
                                   
                         # This code is contributed by Anant Agarwal.                       

C#

                         // C# implementation to find the                       
                         // missing number in shuffled array                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Returns the missing number                       
                                                 // Size of arr2[] is n-1                       
                                                 static                                     int                                     missingNumber(                                     int                                     []arr1,                       
                                                 int                                     []arr2,                       
                                                 int                                     n)                       
                                                 {                       
                                                 // Missing number 'mnum'                       
                                                 int                                     mnum = 0;                       
                                   
                                                 // 1st array is of size 'n'                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 mnum = mnum ^ arr1[i];                       
                                   
                                                 // 2nd array is of size 'n - 1'                       
                                                 for                                     (                                     int                                     i = 0; i < n - 1; i++)                       
                                                 mnum = mnum ^ arr2[i];                       
                                   
                                                 // Required missing number                       
                                                 return                                     mnum;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     []arr1 = {4, 8, 1, 3, 7};                       
                                                 int                                     []arr2 = {7, 4, 3, 1};                       
                                                 int                                     n = arr1.Length;                       
                                   
                                                 Console.Write(                                     "Missing number = "                       
                                                 + missingNumber(arr1, arr2, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal.                       

PHP

                         <?php                       
                         // PHP implementation to find the                       
                         // missing number in shuffled array                       
                         // PHP implementation to find the                       
                         // missing number in shuffled array                       
           
                         // Returns the missing number                       
                         // Size of arr2[] is n-1                       
                         function                                     missingNumber(                                     $arr1                                     ,                                     $arr2                                     ,                       
                                                 $n                                     )                       
                         {                       
                                   
                                                 // Missing number 'mnum'                       
                                                 $mnum                                     = 0;                       
           
                                                 // 1st array is of size 'n'                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $mnum                                     =                                     $mnum                                     ^                                     $arr1                                     [                                     $i                                     ];                       
           
                                                 // 2nd array is of size 'n - 1'                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     - 1;                                     $i                                     ++)                       
                                                 $mnum                                     =                                     $mnum                                     ^                                     $arr2                                     [                                     $i                                     ];                       
           
                                                 // Required missing number                       
                                                 return                                     $mnum                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $arr1                                     =                                     array                                     (4, 8, 1, 3, 7);                       
                                                 $arr2                                     =                                     array                                     (7, 4, 3, 1);                       
                                                 $n                                     =                                     count                                     (                                     $arr1                                     );                       
                                                 echo                                     "Missing number = "                       
                                                 , missingNumber(                                     $arr1                                     ,                                     $arr2                                     ,                                     $n                                     );                       
                                   
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript implementation to find the                       
                         // missing number in shuffled array                       
                         // Javascript implementation to find the                       
                         // missing number in shuffled array                       
           
                         // Returns the missing number                       
                         // Size of arr2[] is n-1                       
                         function                                     missingNumber(arr1, arr2, n)                       
                         {                       
                                                 // Missing number 'mnum'                       
                                                 let mnum = 0;                       
           
                                                 // 1st array is of size 'n'                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 mnum = mnum ^ arr1[i];                       
           
                                                 // 2nd array is of size 'n - 1'                       
                                                 for                                     (let i = 0; i < n - 1; i++)                       
                                                 mnum = mnum ^ arr2[i];                       
           
                                                 // Required missing number                       
                                                 return                                     mnum;                       
                         }                       
           
                         // Driver Code                       
                                                 let arr1 = [4, 8, 1, 3, 7];                       
                                                 let arr2 = [7, 4, 3, 1];                       
                                                 let n = arr1.length;                       
                                                 document.write(                                     "Missing number = "                       
                                                 + missingNumber(arr1, arr2, n));                       
           
                         </script>                       

输出：

Missing number = 8

复杂度：O（n）时间复杂度和O（1）额外空间。本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章