找到两个缺失的数字|集1（一个有趣的线性时间解决方案）-yiteyi-C++库

给定一个由n个唯一整数组成的数组，其中数组中的每个元素都在[1，n]范围内。数组具有所有不同的元素，数组的大小为（n-2）。因此，该数组中缺少两个范围内的数字。找到丢失的两个数字。 例如：

null

Input  : arr[] = {1, 3, 5, 6}Output : 2 4Input : arr[] = {1, 2, 4}Output : 3 5Input : arr[] = {1, 2}Output : 3 4

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

方法1–O（n）时间复杂度和O（n）额外空间

第一步： 以布尔数组为例 做记号 它跟踪数组中存在的所有元素。 第二步： 从1迭代到n，检查每个元素在布尔数组中是否标记为true，如果不是，则只显示该元素。

C++

                         // C++ Program to find two Missing Numbers using O(n)                       
                         // extra space                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find two missing numbers in range                       
                         // [1, n]. This function assumes that size of array                       
                         // is n-2 and all array elements are distinct                       
                         void                                     findTwoMissingNumbers(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Create a boolean vector of size n+1 and                       
                                                 // mark all present elements of arr[] in it.                       
                                                 vector<                                     bool                                     > mark(n+1,                                     false                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < n-2; i++)                       
                                                 mark[arr[i]] =                                     true                                     ;                       
           
                                                 // Print two unmarked elements                       
                                                 cout <<                                     "Two Missing Numbers are"                                     ;                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 if                                     (! mark[i])                       
                                                 cout << i <<                                     " "                                     ;                       
           
                                                 cout << endl;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 3, 5, 6};                       
           
                                                 // Range of numbers is 2 plus size of array                       
                                                 int                                     n = 2 +                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
           
                                                 findTwoMissingNumbers(arr, n);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program to find two Missing Numbers using O(n)                       
                         // extra space                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Function to find two missing numbers in range                       
                         // [1, n]. This function assumes that size of array                       
                         // is n-2 and all array elements are distinct                       
                         static                                     void                                     findTwoMissingNumbers(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Create a boolean vector of size n+1 and                       
                                                 // mark all present elements of arr[] in it.                       
                                                 boolean                                     []mark =                                     new                                     boolean                                     [n+                                     1                                     ];                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n-                                     2                                     ; i++)                       
                                                 mark[arr[i]] =                                     true                                     ;                       
           
                                                 // Print two unmarked elements                       
                                                 System.out.println(                                     "Two Missing Numbers are"                                     );                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 if                                     (! mark[i])                       
                                                 System.out.print(i +                                     " "                                     );                       
           
                                                 System.out.println();                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     3                                     ,                                     5                                     ,                                     6                                     };                       
           
                                                 // Range of numbers is 2 plus size of array                       
                                                 int                                     n =                                     2                                     + arr.length;                       
           
                                                 findTwoMissingNumbers(arr, n);                       
                         }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Python3

                         # Python3 program to find two Missing Numbers using O(n)                       
                         # extra space                       
           
                         # Function to find two missing numbers in range                       
                         # [1, n]. This function assumes that size of array                       
                         # is n-2 and all array elements are distinct                       
                         def                                     findTwoMissingNumbers(arr, n):                       
                                                 # Create a boolean vector of size n+1 and                       
                                                 # mark all present elements of arr[] in it.                       
                                                 mark                                     =                                     [                                     False                                     for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,n                                     -                                     2                                     ,                                     1                                     ):                       
                                                 mark[arr[i]]                                     =                                     True                       
           
                                                 # Print two unmarked elements                       
                                                 print                                     (                                     "Two Missing Numbers are"                                     )                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,n                                     +                                     1                                     ,                                     1                                     ):                       
                                                 if                                     (mark[i]                                     =                                     =                                     False                                     ):                       
                                                 print                                     (i,end                                     =                                     " "                                     )                       
           
                                                 print                                     (                                     ""                                     )                       
           
                         # Driver program to test above function                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 arr                                     =                                     [                                     1                                     ,                                     3                                     ,                                     5                                     ,                                     6                                     ]                       
           
                                                 # Range of numbers is 2 plus size of array                       
                                                 n                                     =                                     2                                     +                                     len                                     (arr)                       
           
                                   
                                                 findTwoMissingNumbers(arr, n);                       
           
                         # This code is contributed by                       
                         # Surendra_Gangwar                       

C#

                         // C# Program to find two Missing Numbers                       
                         // using O(n) extra space                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                                   
                         class                                     GFG                       
                         {                       
           
                         // Function to find two missing numbers in range                       
                         // [1, n]. This function assumes that size of array                       
                         // is n-2 and all array elements are distinct                       
                         static                                     void                                     findTwoMissingNumbers(                                     int                                     []arr,                                     int                                     n)                       
                         {                       
                                                 // Create a boolean vector of size n+1 and                       
                                                 // mark all present elements of arr[] in it.                       
                                                 Boolean []mark =                                     new                                     Boolean[n + 1];                       
                                                 for                                     (                                     int                                     i = 0; i < n - 2; i++)                       
                                                 mark[arr[i]] =                                     true                                     ;                       
           
                                                 // Print two unmarked elements                       
                                                 Console.WriteLine(                                     "Two Missing Numbers are"                                     );                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 if                                     (! mark[i])                       
                                                 Console.Write(i +                                     " "                                     );                       
           
                                                 Console.WriteLine();                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     []arr = {1, 3, 5, 6};                       
           
                                                 // Range of numbers is 2 plus size of array                       
                                                 int                                     n = 2 + arr.Length;                       
           
                                                 findTwoMissingNumbers(arr, n);                       
                         }                       
                         }                       
           
                         // This code contributed by Rajput-Ji                       

Javascript

                         <script>                       
           
                                                 // Javascript Program to find two                       
                                                 // Missing Numbers using O(n) extra space                       
                                   
                                                 // Function to find two missing numbers in range                       
                                                 // [1, n]. This function assumes that size of array                       
                                                 // is n-2 and all array elements are distinct                       
                                                 function                                     findTwoMissingNumbers(arr, n)                       
                                                 {                       
                                                 // Create a boolean vector of size n+1 and                       
                                                 // mark all present elements of arr[] in it.                       
                                                 let mark =                                     new                                     Array(n+1);                       
                                                 for                                     (let i = 0; i < n-2; i++)                       
                                                 mark[arr[i]] =                                     true                                     ;                       
           
                                                 // Print two unmarked elements                       
                                                 document.write(                                     "Two Missing Numbers are"                                     +                                     "</br>"                                     );                       
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 if                                     (!mark[i])                       
                                                 document.write(i +                                     " "                                     );                       
           
                                                 document.write(                                     "</br>"                                     );                       
                                                 }                       
                                   
                                                 let arr = [1, 3, 5, 6];                       
                                   
                                                 // Range of numbers is 2 plus size of array                       
                                                 let n = 2 + arr.length;                       
                                   
                                                 findTwoMissingNumbers(arr, n);                       
           
                         </script>                       

输出：

Two Missing Numbers are2 4

方法2–O（n）时间复杂度和O（1）额外空间

这个想法是基于这查找一个缺失号码的流行解决方案。我们扩展了解决方案，以便打印出两个缺失的元素。让我们找出两个缺失数字的总和：

arrSum => Sum of all elements in the arraysum (Sum of 2 missing numbers) = (Sum of integers from 1 to n) - arrSum                               = ((n)*(n+1))/2 – arrSum avg (Average of 2 missing numbers) = sum / 2;

其中一个数字将小于或等于 平均值 而另一个将严格大于 平均值 .两个数字永远不可能相等，因为所有给定的数字都是不同的。
我们可以找到第一个缺失的数字，即从1到1的自然数之和 平均值 ，即平均*（平均+1）/2 减小于的数组元素之和 平均值
我们可以通过从缺失的数字之和中减去第一个缺失的数字来找到第二个缺失的数字

考虑一个更好的澄清例子

Input : 1 3 5 6, n = 6Sum of missing integers = n*(n+1)/2 - (1+3+5+6) = 6.Average of missing integers = 6/2 = 3.Sum of array elements less than or equal to average = 1 + 3 = 4Sum of natural numbers from 1 to avg = avg*(avg + 1)/2                                     = 3*4/2 = 6First missing number = 6 - 4 = 2Second missing number = Sum of missing integers-First missing numberSecond missing number = 6-2= 4

下面是上述想法的实施。

C++

                         // C++ Program to find 2 Missing Numbers using O(1)                       
                         // extra space                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         // Returns the sum of the array                       
                         int                                     getSum(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 sum += arr[i];                       
                                                 return                                     sum;                       
                         }                       
           
                         // Function to find two missing numbers in range                       
                         // [1, n]. This function assumes that size of array                       
                         // is n-2 and all array elements are distinct                       
                         void                                     findTwoMissingNumbers(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Sum of 2 Missing Numbers                       
                                                 int                                     sum = (n*(n + 1)) /2 - getSum(arr, n-2);                       
           
                                                 // Find average of two elements                       
                                                 int                                     avg = (sum / 2);                       
           
                                                 // Find sum of elements smaller than average (avg)                       
                                                 // and sum of elements greater than average (avg)                       
                                                 int                                     sumSmallerHalf = 0, sumGreaterHalf = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n-2; i++)                       
                                                 {                       
                                                 if                                     (arr[i] <= avg)                       
                                                 sumSmallerHalf += arr[i];                       
                                                 else                       
                                                 sumGreaterHalf += arr[i];                       
                                                 }                       
           
                                                 cout <<                                     "Two Missing Numbers are"                                     ;                       
           
                                                 // The first (smaller) element = (sum of natural                       
                                                 // numbers upto avg) - (sum of array elements                       
                                                 // smaller than or equal to avg)                       
                                                 int                                     totalSmallerHalf = (avg*(avg + 1)) / 2;                       
                                                 int                                     smallerElement = totalSmallerHalf - sumSmallerHalf;                       
                                                 cout << smallerElement <<                                     " "                                     ;                       
           
                                                 // The second (larger) element = (sum of both                       
                                                 // the elements) - smaller element                       
                                                 cout << sum - smallerElement;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 3, 5, 6};                       
                                   
                                                 // Range of numbers is 2 plus size of array                       
                                                 int                                     n = 2 +                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                   
                                                 findTwoMissingNumbers(arr, n);                       
                                   
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program to find 2 Missing                       
                         // Numbers using O(1) extra space                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Returns the sum of the array                       
                         static                                     int                                     getSum(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     sum =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 sum += arr[i];                       
                                                 return                                     sum;                       
                         }                       
           
                         // Function to find two missing                       
                         // numbers in range [1, n]. This                       
                         // function assumes that size of                       
                         // array is n-2 and all array                       
                         // elements are distinct                       
                         static                                     void                                     findTwoMissingNumbers(                                     int                                     arr[],                       
                                                 int                                     n)                       
                         {                       
                                                 // Sum of 2 Missing Numbers                       
                                                 int                                     sum = (n * (n +                                     1                                     )) /                       
                                                 2                                     - getSum(arr, n -                                     2                                     );                       
           
                                                 // Find average of two elements                       
                                                 int                                     avg = (sum /                                     2                                     );                       
           
                                                 // Find sum of elements smaller                       
                                                 // than average (avg) and sum of                       
                                                 // elements greater than average (avg)                       
                                                 int                                     sumSmallerHalf =                                     0                                     ,                       
                                                 sumGreaterHalf =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n -                                     2                                     ; i++)                       
                                                 {                       
                                                 if                                     (arr[i] <= avg)                       
                                                 sumSmallerHalf += arr[i];                       
                                                 else                       
                                                 sumGreaterHalf += arr[i];                       
                                                 }                       
           
                                                 System.out.println(                                     "Two Missing "                                     +                       
                                                 "Numbers are"                                     );                       
           
                                                 // The first (smaller) element =                       
                                                 // (sum of natural numbers upto                       
                                                 // avg) - (sum of array elements                       
                                                 // smaller than or equal to avg)                       
                                                 int                                     totalSmallerHalf = (avg *                       
                                                 (avg +                                     1                                     )) /                                     2                                     ;                       
                                                 System.out.println(totalSmallerHalf -                       
                                                 sumSmallerHalf);                       
           
                                                 // The first (smaller) element =                       
                                                 // (sum of natural numbers from                       
                                                 // avg+1 to n) - (sum of array                       
                                                 // elements greater than avg)                       
                                                 System.out.println(((n * (n +                                     1                                     )) /                                     2                                     -                       
                                                 totalSmallerHalf) -                       
                                                 sumGreaterHalf);                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                         int                                     arr[] = {                                     1                                     ,                                     3                                     ,                                     5                                     ,                                     6                                     };                       
                                   
                         // Range of numbers is 2                       
                         // plus size of array                       
                         int                                     n =                                     2                                     + arr.length;                       
                                   
                         findTwoMissingNumbers(arr, n);                       
                         }                       
                         }                       
           
                         // This code is contributed by aj_36                       

Python3

                         # Python Program to find 2 Missing                       
                         # Numbers using O(1) extra space                       
           
                         # Returns the sum of the array                       
                         def                                     getSum(arr,n):                       
           
                                                 sum                                     =                                     0                                     ;                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                                 sum                                     +                                     =                                     arr[i]                       
                                                 return                                     sum                       
           
                         # Function to find two missing                       
                         # numbers in range [1, n]. This                       
                         # function assumes that size of                       
                         # array is n-2 and all array                       
                         # elements are distinct                       
                         def                                     findTwoMissingNumbers(arr, n):                       
           
                                                 # Sum of 2 Missing Numbers                       
                                                 sum                                     =                                     ((n                                     *                                     (n                                     +                                     1                                     ))                                     /                                     2                                     -                       
                                                 getSum(arr, n                                     -                                     2                                     ));                       
           
                                                 #Find average of two elements                       
                                                 avg                                     =                                     (                                     sum                                     /                                     2                                     );                       
           
                                                 # Find sum of elements smaller                       
                                                 # than average (avg) and sum                       
                                                 # of elements greater than                       
                                                 # average (avg)                       
                                                 sumSmallerHalf                                     =                                     0                       
                                                 sumGreaterHalf                                     =                                     0                                     ;                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n                                     -                                     2                                     ):                       
                                   
                                                 if                                     (arr[i] <                                     =                                     avg):                       
                                                 sumSmallerHalf                                     +                                     =                                     arr[i]                       
                                                 else                                     :                       
                                                 sumGreaterHalf                                     +                                     =                                     arr[i]                       
                                   
                                                 print                                     (                                     "Two Missing Numbers are"                                     )                       
           
                                                 # The first (smaller) element = (sum                       
                                                 # of natural numbers upto avg) - (sum                       
                                                 # of array elements smaller than or                       
                                                 # equal to avg)                       
                                                 totalSmallerHalf                                     =                                     (avg                                     *                                     (avg                                     +                                     1                                     ))                                     /                                     2                       
                                                 print                                     (                                     str                                     (totalSmallerHalf                                     -                       
                                                 sumSmallerHalf)                                     +                                     " "                                     )                       
           
                                                 # The first (smaller) element = (sum                       
                                                 # of natural numbers from avg+1 to n) -                       
                                                 # (sum of array elements greater than avg)                       
                                                 print                                     (                                     str                                     (((n                                     *                                     (n                                     +                                     1                                     ))                                     /                                     2                                     -                       
                                                 totalSmallerHalf)                                     -                       
                                                 sumGreaterHalf))                       
           
                         # Driver Code                       
                         arr                                     =                                     [                                     1                                     ,                                     3                                     ,                                     5                                     ,                                     6                                     ]                       
                                   
                         # Range of numbers is 2                       
                         # plus size of array                       
                         n                                     =                                     2                                     +                                     len                                     (arr)                       
                                   
                         findTwoMissingNumbers(arr, n)                       
           
                         # This code is contributed                       
                         # by Yatin Gupta                       

C#

                         // C# Program to find 2 Missing                       
                         // Numbers using O(1) extra space                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // Returns the sum of the array                       
                         static                                     int                                     getSum(                                     int                                     []arr,                                     int                                     n)                       
                         {                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 sum += arr[i];                       
                                                 return                                     sum;                       
                         }                       
           
                         // Function to find two missing                       
                         // numbers in range [1, n]. This                       
                         // function assumes that size of                       
                         // array is n-2 and all array                       
                         // elements are distinct                       
                         static                                     void                                     findTwoMissingNumbers(                                     int                                     []arr,                       
                                                 int                                     n)                       
                         {                       
                                                 // Sum of 2 Missing Numbers                       
                                                 int                                     sum = (n * (n + 1)) / 2 -                       
                                                 getSum(arr, n - 2);                       
           
                                                 // Find average of two elements                       
                                                 int                                     avg = (sum / 2);                       
           
                                                 // Find sum of elements smaller                       
                                                 // than average (avg) and sum of                       
                                                 // elements greater than average (avg)                       
                                                 int                                     sumSmallerHalf = 0,                       
                                                 sumGreaterHalf = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n - 2; i++)                       
                                                 {                       
                                                 if                                     (arr[i] <= avg)                       
                                                 sumSmallerHalf += arr[i];                       
                                                 else                       
                                                 sumGreaterHalf += arr[i];                       
                                                 }                       
           
                                                 Console.WriteLine(                                     "Two Missing "                                     +                       
                                                 "Numbers are "                                     );                       
           
                                                 // The first (smaller) element =                       
                                                 // (sum of natural numbers upto                       
                                                 // avg) - (sum of array elements                       
                                                 // smaller than or equal to avg)                       
                                                 int                                     totalSmallerHalf = (avg *                       
                                                 (avg + 1)) / 2;                       
                                                 Console.WriteLine(totalSmallerHalf -                       
                                                 sumSmallerHalf);                       
           
                                                 // The first (smaller) element =                       
                                                 // (sum of natural numbers from                       
                                                 // avg+1 to n) - (sum of array                       
                                                 // elements greater than avg)                       
                                                 Console.WriteLine(((n * (n + 1)) / 2 -                       
                                                 totalSmallerHalf) -                       
                                                 sumGreaterHalf);                       
                         }                       
           
                         // Driver Code                       
                         static                                     public                                     void                                     Main ()                       
                         {                       
                                                 int                                     []arr = {1, 3, 5, 6};                       
                                   
                                                 // Range of numbers is 2                       
                                                 // plus size of array                       
                                                 int                                     n = 2 + arr.Length;                       
                                   
                                                 findTwoMissingNumbers(arr, n);                       
                         }                       
                         }                       
           
                         // This code is contributed by ajit                       

PHP

                         <?php                       
                         // PHP Program to find 2 Missing                       
                         // Numbers using O(1) extra space                       
           
                         // Returns the sum of the array                       
                         function                                     getSum(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 $sum                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $sum                                     +=                                     $arr                                     [                                     $i                                     ];                       
                                                 return                                     $sum                                     ;                       
                         }                       
           
                         // Function to find two missing                       
                         // numbers in range [1, n]. This                       
                         // function assumes that size of                       
                         // array is n-2 and all array                       
                         // elements are distinct                       
                         function                                     findTwoMissingNumbers(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 // Sum of 2 Missing Numbers                       
                                                 $sum                                     = (                                     $n                                     * (                                     $n                                     + 1)) /2 -                       
                                                 getSum(                                     $arr                                     ,                                     $n                                     - 2);                       
           
                                                 // Find average of two elements                       
                                                 $avg                                     = (                                     $sum                                     / 2);                       
           
                                                 // Find sum of elements smaller                       
                                                 // than average (avg) and sum of                       
                                                 // elements greater than average (avg)                       
                                                 $sumSmallerHalf                                     = 0;                       
                                                 $sumGreaterHalf                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     - 2;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $arr                                     [                                     $i                                     ] <=                                     $avg                                     )                       
                                                 $sumSmallerHalf                                     +=                                     $arr                                     [                                     $i                                     ];                       
                                                 else                       
                                                 $sumGreaterHalf                                     +=                                     $arr                                     [                                     $i                                     ];                       
                                                 }                       
           
                                                 echo                                     "Two Missing Numbers are"                                     ;                       
           
                                                 // The first (smaller) element =                       
                                                 // (sum of natural numbers upto avg) -                       
                                                 // (sum of array elements smaller                       
                                                 // than or equal to avg)                       
                                                 $totalSmallerHalf                                     = (                                     $avg                                     * (                                     $avg                                     + 1)) / 2;                       
                                                 echo                                     (                                     $totalSmallerHalf                                     -                       
                                                 $sumSmallerHalf                                     ) ,                                     " "                                     ;                       
           
                                                 // The first (smaller) element =                       
                                                 // (sum of natural numbers from avg +                       
                                                 // 1 to n) - (sum of array elements                       
                                                 // greater than avg)                       
                                                 echo                                     (((                                     $n                                     * (                                     $n                                     + 1)) / 2 -                                     $totalSmallerHalf                                     ) -                       
                                                 $sumGreaterHalf                                     );                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (1, 3, 5, 6);                       
           
                         // Range of numbers is                       
                         // 2 plus size of array                       
                         $n                                     = 2 + sizeof(                                     $arr                                     );                       
           
                         findTwoMissingNumbers(                                     $arr                                     ,                                     $n                                     );                       
           
                         // This code is contributed by aj_36                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // Javascript Program to find 2 Missing                       
                                                 // Numbers using O(1) extra space                       
                                   
                                                 // Returns the sum of the array                       
                                                 function                                     getSum(arr, n)                       
                                                 {                       
                                                 let sum = 0;                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 sum += arr[i];                       
                                                 return                                     sum;                       
                                                 }                       
           
                                                 // Function to find two missing                       
                                                 // numbers in range [1, n]. This                       
                                                 // function assumes that size of                       
                                                 // array is n-2 and all array                       
                                                 // elements are distinct                       
                                                 function                                     findTwoMissingNumbers(arr, n)                       
                                                 {                       
                                                 // Sum of 2 Missing Numbers                       
                                                 let sum = (n * (n + 1)) / 2 -                       
                                                 getSum(arr, n - 2);                       
           
                                                 // Find average of two elements                       
                                                 let avg = (sum / 2);                       
           
                                                 // Find sum of elements smaller                       
                                                 // than average (avg) and sum of                       
                                                 // elements greater than average (avg)                       
                                                 let sumSmallerHalf = 0,                       
                                                 sumGreaterHalf = 0;                       
                                                 for                                     (let i = 0; i < n - 2; i++)                       
                                                 {                       
                                                 if                                     (arr[i] <= avg)                       
                                                 sumSmallerHalf += arr[i];                       
                                                 else                       
                                                 sumGreaterHalf += arr[i];                       
                                                 }                       
           
                                                 document.write(                       
                                                 "Two Missing "                                     +                                     "Numbers are "                                     +                                     "</br>"                       
                                                 );                       
           
                                                 // The first (smaller) element =                       
                                                 // (sum of natural numbers upto                       
                                                 // avg) - (sum of array elements                       
                                                 // smaller than or equal to avg)                       
                                                 let totalSmallerHalf = (avg * (avg + 1)) / 2;                       
                                                 document.write(                       
                                                 (totalSmallerHalf - sumSmallerHalf) +                                     " "                       
                                                 );                       
           
                                                 // The first (smaller) element =                       
                                                 // (sum of natural numbers from                       
                                                 // avg+1 to n) - (sum of array                       
                                                 // elements greater than avg)                       
                                                 document.write(                       
                                                 ((n * (n + 1)) / 2 - totalSmallerHalf) -                       
                                                 sumGreaterHalf +                                     "</br>"                       
                                                 );                       
                                                 }                       
                                   
                                                 let arr = [1, 3, 5, 6];                       
                                   
                                                 // Range of numbers is 2                       
                                                 // plus size of array                       
                                                 let n = 2 + arr.length;                       
                                   
                                                 findTwoMissingNumbers(arr, n);                       
           
                         </script>                       

输出：

Two Missing Numbers are2 4

注意：上述解决方案可能存在溢出问题。在下面的集合2中，讨论了另一种解决方案，即O（n）时间，O（1）空间，并且不会导致溢出问题。查找两个缺失的数字|集合2（基于异或的解决方案）本文由 希拉格·阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章