Numărul depășit al fiecărui element în tablou
Având în vedere o serie de numere întregi distincte arr [] a depășește a unui element arr [i] este orice element arr [j] astfel încât j> i și arr [j]> arr [i]. Găsiți numărul de suprapas pentru fiecare element din tablou.
Exemple:
Intrare: arr [] = [2 7 5 3 8 1]
Ieșire: [4 1 1 1 0 0]
Explicaţie: Pentru 2 există 4 elemente mai mari la dreapta: [7 5 3 8]
Pentru 7 există un element mai mare la dreapta sa: [8]
Pentru 5 există un element mai mare la dreapta sa: [8]
Pentru 3 există un element mai mare la dreapta sa: [8]
Pentru 8 nu există un element mai mare la dreapta sa: [0]
Pentru 1 nu există un element mai mare la dreapta sa: [0]Intrare: arr [] = [4 5 1]
Ieșire: [1 0 0]
Explicaţie: Pentru 4 există un element mai mare la dreapta sa: [5]
Pentru 5 nu există un element mai mare la dreapta sa: [0]
Pentru 1 nu există un element mai mare la dreapta sa: [0]
Tabel de conținut
- [Abordare naivă] - folosind două bucle cuibărite - O (n^2) Timp și O (1) Spațiu
- [Abordare preconizată] - Utilizarea pasului de îmbinare a sortării de îmbinare - o (n log n) timp și o (n) spațiu
[Abordare naivă] - folosind două bucle cuibărite - O (n^2) Timp și O (1) Spațiu
Cea mai simplă abordare este să repeta prin tablou și pentru fiecare element conta numărul de elemente pentru corect adică mai mare decât el.
C++ #include #include using namespace std ; vector < int > findSurpasser ( vector < int > & arr ) { int n = arr . size (); // array to store surpasser counts vector < int > res ( n 0 ); for ( int i = 0 ; i < n ; i ++ ) { // Find surpasser for arr[i] int count = 0 ; for ( int j = i + 1 ; j < n ; j ++ ) { if ( arr [ j ] > arr [ i ]) count ++ ; } res [ i ] = count ; } return res ; } int main () { vector < int > arr = { 2 7 5 3 8 1 }; vector < int > res = findSurpasser ( arr ); for ( int count : res ) cout < < count < < ' ' ; return 0 ; }
C #include #include int * findSurpasser ( int arr [] int n ) { // Array to store surpasser counts int * res = ( int * ) malloc ( n * sizeof ( int )); for ( int i = 0 ; i < n ; i ++ ) { // Find surpasser for arr[i] int count = 0 ; for ( int j = i + 1 ; j < n ; j ++ ) { if ( arr [ j ] > arr [ i ]) count ++ ; } res [ i ] = count ; } return res ; } int main () { int arr [] = { 2 7 5 3 8 1 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int * res = findSurpasser ( arr n ); for ( int i = 0 ; i < n ; i ++ ) printf ( '%d ' res [ i ]); return 0 ; }
Java import java.util.ArrayList ; class GfG { static ArrayList < Integer > findSurpasser ( int [] arr ) { int n = arr . length ; // List to store surpasser counts ArrayList < Integer > res = new ArrayList <> (); for ( int i = 0 ; i < n ; i ++ ) { // Find surpasser for arr[i] int count = 0 ; for ( int j = i + 1 ; j < n ; j ++ ) { if ( arr [ j ] > arr [ i ] ) count ++ ; } res . add ( count ); } return res ; } public static void main ( String [] args ) { int [] arr = { 2 7 5 3 8 1 }; ArrayList < Integer > res = findSurpasser ( arr ); for ( int count : res ) System . out . print ( count + ' ' ); } }
Python def findSurpasser ( arr ): n = len ( arr ) # List to store surpasser counts res = [ 0 ] * n for i in range ( n ): # Find surpasser for arr[i] count = 0 for j in range ( i + 1 n ): if arr [ j ] > arr [ i ]: count += 1 res [ i ] = count return res if __name__ == '__main__' : arr = [ 2 7 5 3 8 1 ] result = findSurpasser ( arr ) for val in result : print ( val end = ' ' )
C# using System ; using System.Collections.Generic ; class GfG { static List < int > findSurpasser ( int [] arr ) { int n = arr . Length ; // List to store surpasser counts List < int > res = new List < int > (); for ( int i = 0 ; i < n ; i ++ ) { // Find surpasser for arr[i] int count = 0 ; for ( int j = i + 1 ; j < n ; j ++ ) { if ( arr [ j ] > arr [ i ]) count ++ ; } res . Add ( count ); } return res ; } static void Main ( string [] args ) { int [] arr = { 2 7 5 3 8 1 }; List < int > result = findSurpasser ( arr ); foreach ( int count in result ) Console . Write ( count + ' ' ); } }
JavaScript function findSurpasser ( arr ) { const n = arr . length ; // array to store surpasser counts let res = new Array ( n ). fill ( 0 ); for ( let i = 0 ; i < n ; i ++ ) { // Find surpasser for arr[i] let count = 0 ; for ( let j = i + 1 ; j < n ; j ++ ) { if ( arr [ j ] > arr [ i ]) count ++ ; } res [ i ] = count ; } return res ; } // Driver Code const arr = [ 2 7 5 3 8 1 ]; const result = findSurpasser ( arr ); console . log ( result . join ( ' ' ));
Ieșire
4 1 1 1 0 0
[Abordare preconizată] - Utilizarea pasului de îmbinare a sortării de îmbinare - o (n log n) timp și o (n) spațiu
În această abordare folosim Fuzionați pasul de merge sort . În timpul fuziunii dacă ith elementul din jumătatea stângă este mai mic decât jth element în jumătatea dreaptă înseamnă că totul rămas elemente în jumătatea dreaptă (de la j la sfârșit) sunt mai mare decât ith element în jumătatea stângă (deoarece ambele jumătăți sunt sortat ) Prin urmare, adăugăm numărul de elemente rămase în jumătatea dreaptă până la depășirea numărului din ith elementul jumătății stângi. Acest proces se repetă pentru toate elementele din jumătatea stângă, deoarece sunt contopite cu jumătatea dreaptă.
Deoarece toate elementele din tablou sunt distinct Folosim un Harta hash Pentru a menține depozitul numărului de suprapas pentru fiecare element. După ce sortarea de îmbinare este completă, completăm tabloul de rezultate cu numărul de supraveghere menținând aceeași ordine ca și intrarea inițială.
C++ #include #include #include using namespace std ; // Merge function to sort the array and update surpasser counts int merge ( vector < int > & arr int lo int mid int hi unordered_map < int int > & m ) { int n1 = mid - lo + 1 ; int n2 = hi - mid ; vector < int > left ( n1 ) right ( n2 ); // Copy data into temporary arrays left[] and right[] for ( int i = 0 ; i < n1 ; i ++ ) left [ i ] = arr [ lo + i ]; for ( int j = 0 ; j < n2 ; j ++ ) right [ j ] = arr [ mid + 1 + j ]; int i = 0 j = 0 k = lo ; // Merging two halves while ( i < n1 && j < n2 ) { // All elements in right[j..n2] are greater than left[i] // So add n2 - j in surpasser count of left[i] if ( left [ i ] < right [ j ]) { m [ left [ i ]] += n2 - j ; arr [ k ++ ] = left [ i ++ ]; } else { arr [ k ++ ] = right [ j ++ ]; } } // Copy remaining elements of left[] if any while ( i < n1 ) arr [ k ++ ] = left [ i ++ ]; // Copy remaining elements of right[] if any while ( j < n2 ) arr [ k ++ ] = right [ j ++ ]; } void mergeSort ( vector < int > & arr int lo int hi unordered_map < int int > & m ) { if ( lo < hi ) { int mid = lo + ( hi - lo ) / 2 ; // Sort left and right half mergeSort ( arr lo mid m ); mergeSort ( arr mid + 1 hi m ); // Merge them merge ( arr lo mid hi m ); } } vector < int > findSurpasser ( vector < int >& arr ) { int n = arr . size (); // Map to store surpasser counts unordered_map < int int > m ; // Duplicate array to perform merge Sort // so that orginial array is not modified vector < int > dup = arr ; mergeSort ( dup 0 n - 1 m ); // Store surpasser counts in result array // in the same order as given array vector < int > res ( n ); for ( int i = 0 ; i < n ; i ++ ) res [ i ] = m [ arr [ i ]]; return res ; } int main () { vector < int > arr = { 2 7 5 3 8 1 }; vector < int > res = findSurpasser ( arr ); for ( int count : res ) cout < < count < < ' ' ; return 0 ; }
Java import java.util.List ; import java.util.Map ; import java.util.HashMap ; import java.util.ArrayList ; class GfG { // Merge function to sort the array // and update surpasser counts static void merge ( int [] arr int lo int mid int hi Map < Integer Integer > m ) { int n1 = mid - lo + 1 ; int n2 = hi - mid ; int [] left = new int [ n1 ] ; int [] right = new int [ n2 ] ; // Copy data into temporary arrays left[] and right[] for ( int i = 0 ; i < n1 ; i ++ ) left [ i ] = arr [ lo + i ] ; for ( int j = 0 ; j < n2 ; j ++ ) right [ j ] = arr [ mid + 1 + j ] ; int i = 0 j = 0 k = lo ; // Merging two halves while ( i < n1 && j < n2 ) { // All elements in right[j..n2] are greater than left[i] // So add n2 - j to surpasser count of left[i] if ( left [ i ] < right [ j ] ) { m . put ( left [ i ] m . getOrDefault ( left [ i ] 0 ) + n2 - j ); arr [ k ++] = left [ i ++] ; } else { arr [ k ++] = right [ j ++] ; } } // Copy remaining elements of left[] if any while ( i < n1 ) arr [ k ++] = left [ i ++] ; // Copy remaining elements of right[] if any while ( j < n2 ) arr [ k ++] = right [ j ++] ; } static void mergeSort ( int [] arr int lo int hi Map < Integer Integer > m ) { if ( lo < hi ) { int mid = lo + ( hi - lo ) / 2 ; // Sort left and right halves mergeSort ( arr lo mid m ); mergeSort ( arr mid + 1 hi m ); // Merge them merge ( arr lo mid hi m ); } } static ArrayList < Integer > findSurpasser ( int [] arr ) { int n = arr . length ; // Map to store surpasser counts Map < Integer Integer > m = new HashMap <> (); // Duplicate array to perform merge sort int [] dup = arr . clone (); mergeSort ( dup 0 n - 1 m ); // Store surpasser counts in result list ArrayList < Integer > res = new ArrayList <> (); for ( int i = 0 ; i < n ; i ++ ) res . add ( m . getOrDefault ( arr [ i ] 0 )); return res ; } public static void main ( String [] args ) { int [] arr = { 2 7 5 3 8 1 }; ArrayList < Integer > res = findSurpasser ( arr ); for ( int count : res ) System . out . print ( count + ' ' ); } }
Python def merge ( arr lo mid hi m ): n1 = mid - lo + 1 n2 = hi - mid left = arr [ lo : lo + n1 ] right = arr [ mid + 1 : mid + 1 + n2 ] i = j = 0 k = lo # Merging two halves while i < n1 and j < n2 : # All elements in right[j..n2] are greater than left[i] # So add n2 - j in surpasser count of left[i] if left [ i ] < right [ j ]: m [ left [ i ]] += n2 - j arr [ k ] = left [ i ] i += 1 else : arr [ k ] = right [ j ] j += 1 k += 1 # Copy remaining elements of left[] if any while i < n1 : arr [ k ] = left [ i ] i += 1 k += 1 # Copy remaining elements of right[] if any while j < n2 : arr [ k ] = right [ j ] j += 1 k += 1 def mergeSort ( arr lo hi m ): if lo < hi : mid = lo + ( hi - lo ) // 2 # Sort left and right half mergeSort ( arr lo mid m ) mergeSort ( arr mid + 1 hi m ) # Merge them merge ( arr lo mid hi m ) def findSurpasser ( arr ): n = len ( arr ) # Map to store surpasser counts m = { key : 0 for key in arr } # Duplicate array to perform merge Sort # so that original array is not modified dup = arr [:] mergeSort ( dup 0 n - 1 m ) # Store surpasser counts in result array # in the same order as given array res = [ m [ arr [ i ]] for i in range ( n )] return res if __name__ == '__main__' : arr = [ 2 7 5 3 8 1 ] result = findSurpasser ( arr ) for val in result : print ( val end = ' ' )
C# using System ; using System.Collections.Generic ; class GfG { // Merge function to sort the array // and update surpasser counts static void merge ( int [] arr int lo int mid int hi Dictionary < int int > m ) { int n1 = mid - lo + 1 ; int n2 = hi - mid ; int [] left = new int [ n1 ]; int [] right = new int [ n2 ]; // Copy data into temporary arrays for ( int i = 0 ; i < n1 ; i ++ ) left [ i ] = arr [ lo + i ]; for ( int j = 0 ; j < n2 ; j ++ ) right [ j ] = arr [ mid + 1 + j ]; int i1 = 0 j1 = 0 k = lo ; // Merge the two halves while ( i1 < n1 && j1 < n2 ) { // Count surpassers if ( left [ i1 ] < right [ j1 ]) { if ( ! m . ContainsKey ( left [ i1 ])) m [ left [ i1 ]] = 0 ; m [ left [ i1 ]] += n2 - j1 ; arr [ k ++ ] = left [ i1 ++ ]; } else { arr [ k ++ ] = right [ j1 ++ ]; } } // Copy remaining elements while ( i1 < n1 ) arr [ k ++ ] = left [ i1 ++ ]; while ( j1 < n2 ) arr [ k ++ ] = right [ j1 ++ ]; } static void mergeSort ( int [] arr int lo int hi Dictionary < int int > m ) { if ( lo < hi ) { int mid = lo + ( hi - lo ) / 2 ; // Recursive sort mergeSort ( arr lo mid m ); mergeSort ( arr mid + 1 hi m ); // Merge sorted halves merge ( arr lo mid hi m ); } } static List < int > findSurpasser ( int [] arr ) { int n = arr . Length ; Dictionary < int int > m = new Dictionary < int int > (); int [] dup = new int [ n ]; Array . Copy ( arr dup n ); mergeSort ( dup 0 n - 1 m ); List < int > res = new List < int > (); for ( int i = 0 ; i < n ; i ++ ) { res . Add ( m . ContainsKey ( arr [ i ]) ? m [ arr [ i ]] : 0 ); } return res ; } static void Main () { int [] arr = { 2 7 5 3 8 1 }; List < int > res = findSurpasser ( arr ); foreach ( int count in res ) Console . Write ( count + ' ' ); } }
JavaScript function merge ( arr lo mid hi m ) { const n1 = mid - lo + 1 ; const n2 = hi - mid ; const left = []; const right = []; // Copy data into temporary arrays left[] and right[] for ( let i = 0 ; i < n1 ; i ++ ) left [ i ] = arr [ lo + i ]; for ( let j = 0 ; j < n2 ; j ++ ) right [ j ] = arr [ mid + 1 + j ]; let i = 0 j = 0 k = lo ; // Merging two halves while ( i < n1 && j < n2 ) { // All elements in right[j..n2] are greater than left[i] // So add n2 - j in surpasser count of left[i] if ( left [ i ] < right [ j ]) { m [ left [ i ]] = ( m [ left [ i ]] || 0 ) + n2 - j ; arr [ k ++ ] = left [ i ++ ]; } else { arr [ k ++ ] = right [ j ++ ]; } } // Copy remaining elements of left[] if any while ( i < n1 ) arr [ k ++ ] = left [ i ++ ]; // Copy remaining elements of right[] if any while ( j < n2 ) arr [ k ++ ] = right [ j ++ ]; } function mergeSort ( arr lo hi m ) { if ( lo < hi ) { const mid = Math . floor ( lo + ( hi - lo ) / 2 ); // Sort left and right half mergeSort ( arr lo mid m ); mergeSort ( arr mid + 1 hi m ); // Merge them merge ( arr lo mid hi m ); } } function findSurpasser ( arr ) { const n = arr . length ; // Map to store surpasser counts const m = {}; // Duplicate array to perform merge Sort // so that original array is not modified const dup = arr . slice (); mergeSort ( dup 0 n - 1 m ); // Store surpasser counts in result array // in the same order as given array const res = []; for ( let i = 0 ; i < n ; i ++ ) res . push ( m [ arr [ i ]] || 0 ); return res ; } // Driver Code const arr = [ 2 7 5 3 8 1 ]; const res = findSurpasser ( arr ); console . log ( res . join ( ' ' ));
Ieșire
4 1 1 1 0 0
Articole înrudite:
- Număr de inversare
- Merge Sort
