Find to manglende tal | Sæt 1 (En interessant lineær tidsløsning)
Givet en matrix af n unikke heltal, hvor hvert element i matrixen er i området [1 n]. Arrayet har alle distinkte elementer og størrelsen af arrayet er (n-2). Derfor mangler der to tal fra området i denne matrix. Find de to manglende tal.
Eksempler:
Input : arr[] = {1 3 5 6} Output : 2 4 Input : arr[] = {1 2 4} Output : 3 5 Input : arr[] = {1 2} Output : 3 4 Metode 1 - O(n) tidskompleksitet og O(n) Ekstrarum
Trin 1: Tag et boolesk array mærke der holder styr på alle de elementer, der er til stede i arrayet.
Trin 2: Gentag fra 1 til n tjek for hvert element, hvis det er markeret som sandt i det booleske array, hvis ikke, så vis blot det element.
// C++ Program to find two Missing Numbers using O(n) // extra space #include 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 n ' ; 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 ( ' n ' ) # 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' + ' ' ); for ( let i = 1 ; i <= n ; i ++ ) if ( ! mark [ i ]) document . write ( i + ' ' ); document . write ( ' ' ); } let arr = [ 1 3 5 6 ]; // Range of numbers is 2 plus size of array let n = 2 + arr . length ; findTwoMissingNumbers ( arr n ); < /script>
Produktion
Two Missing Numbers are 2 4
Metode 2 - O(n) tidskompleksitet og O(1) Ekstrarum
Ideen er baseret på denne populær løsning til at finde et manglende nummer. Vi udvider løsningen, så to manglende elementer printes.
Lad os finde ud af summen af 2 manglende tal:
arrSum => Sum of all elements in the array sum (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;
- Et af tallene vil være mindre end eller lig med gns mens den anden vil være strengt taget større end gns . To tal kan aldrig være ens, da alle de givne tal er forskellige.
- Vi kan finde det første manglende tal som en sum af naturlige tal fra 1 til gns dvs. gennemsnit*(gennemsnit+1)/2 minus summen af array-elementer mindre end gns
- Vi kan finde det andet manglende tal ved at trække det første manglende tal fra summen af manglende tal
Overvej et eksempel for bedre afklaring
Input : 1 3 5 6 n = 6 Sum 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 = 4 Sum of natural numbers from 1 to avg = avg*(avg + 1)/2 = 3*4/2 = 6 First missing number = 6 - 4 = 2 Second missing number = Sum of missing integers-First missing number Second missing number = 6-2= 4
Nedenfor er implementeringen af ovenstående idé.
C++ // C++ Program to find 2 Missing Numbers using O(1) // extra space #include 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 n ' ; // 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 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 n ' ; // 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 ' + ' ' ); // 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 + ' ' ); } let arr = [ 1 3 5 6 ]; // Range of numbers is 2 // plus size of array let n = 2 + arr . length ; findTwoMissingNumbers ( arr n ); < /script>
Produktion
Two Missing Numbers are 2 4
Bemærk: Der kan være overløbsproblemer i ovenstående løsning.
I nedenstående sæt 2 diskuteres en anden løsning, der er O(n) tid O(1) plads og ikke forårsager overløbsproblemer.
Find to manglende tal | Sæt 2 (XOR baseret løsning)
