Trouver un indice d'élément maximal apparaissant avec une probabilité égale
Étant donné un tableau d'entiers, recherchez l'élément le plus présent du tableau et renvoyez l'un de ses index de manière aléatoire avec une probabilité égale.
Exemples :
Input: arr[] = [-1 4 9 7 7 2 7 3 0 9 6 5 7 8 9] Output: Element with maximum frequency present at index 6 OR Element with maximum frequency present at Index 3 OR Element with maximum frequency present at index 4 OR Element with maximum frequency present at index 12 All outputs above have equal probability.
L'idée est de parcourir le tableau une fois et de découvrir l'élément maximum apparaissant et sa fréquence n. Ensuite, nous générons un nombre aléatoire r compris entre 1 et n et renvoyons enfin la rième occurrence de l'élément maximal apparaissant dans le tableau.
Vous trouverez ci-dessous la mise en œuvre de l’idée ci-dessus –
// C++ program to return index of most occurring element // of the array randomly with equal probability #include #include #include using namespace std ; // Function to return index of most occurring element // of the array randomly with equal probability void findRandomIndexOfMax ( int arr [] int n ) { // freq store frequency of each element in the array unordered_map < int int > freq ; for ( int i = 0 ; i < n ; i ++ ) freq [ arr [ i ]] += 1 ; int max_element ; // stores max occurring element // stores count of max occurring element int max_so_far = INT_MIN ; // traverse each pair in map and find maximum // occurring element and its frequency for ( pair < int int > p : freq ) { if ( p . second > max_so_far ) { max_so_far = p . second ; max_element = p . first ; } } // generate a random number between [1 max_so_far] int r = ( rand () % max_so_far ) + 1 ; // traverse array again and return index of rth // occurrence of max element for ( int i = 0 count = 0 ; i < n ; i ++ ) { if ( arr [ i ] == max_element ) count ++ ; // print index of rth occurrence of max element if ( count == r ) { cout < < 'Element with maximum frequency present ' 'at index ' < < i < < endl ; break ; } } } // Driver code int main () { // input array int arr [] = { -1 4 9 7 7 2 7 3 0 9 6 5 7 8 9 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); // randomize seed srand ( time ( NULL )); findRandomIndexOfMax ( arr n ); return 0 ; }
Java // Java program to return index of most occurring element // of the array randomly with equal probability import java.util.* ; class GFG { // Function to return index of most occurring element // of the array randomly with equal probability static void findRandomIndexOfMax ( int arr [] int n ) { // freq store frequency of each element in the array HashMap < Integer Integer > mp = new HashMap < Integer Integer > (); for ( int i = 0 ; i < n ; i ++ ) if ( mp . containsKey ( arr [ i ] )) { mp . put ( arr [ i ] mp . get ( arr [ i ] ) + 1 ); } else { mp . put ( arr [ i ] 1 ); } int max_element = Integer . MIN_VALUE ; // stores max occurring element // stores count of max occurring element int max_so_far = Integer . MIN_VALUE ; // traverse each pair in map and find maximum // occurring element and its frequency for ( Map . Entry < Integer Integer > p : mp . entrySet ()) { if ( p . getValue () > max_so_far ) { max_so_far = p . getValue (); max_element = p . getKey (); } } // generate a random number between [1 max_so_far] int r = ( int ) (( new Random (). nextInt ( max_so_far ) % max_so_far ) + 1 ); // traverse array again and return index of rth // occurrence of max element for ( int i = 0 count = 0 ; i < n ; i ++ ) { if ( arr [ i ] == max_element ) count ++ ; // print index of rth occurrence of max element if ( count == r ) { System . out . print ( 'Element with maximum frequency present ' + 'at index ' + i + 'n' ); break ; } } } // Driver code public static void main ( String [] args ) { // input array int arr [] = { - 1 4 9 7 7 2 7 3 0 9 6 5 7 8 9 }; int n = arr . length ; findRandomIndexOfMax ( arr n ); } } // This code is contributed by Rajput-Ji
Python3 # Python3 program to return index of most occurring element # of the array randomly with equal probability import random # Function to return index of most occurring element # of the array randomly with equal probability def findRandomIndexOfMax ( arr n ): # freq store frequency of each element in the array mp = dict () for i in range ( n ) : if ( arr [ i ] in mp ): mp [ arr [ i ]] = mp [ arr [ i ]] + 1 else : mp [ arr [ i ]] = 1 max_element = - 323567 # stores max occurring element # stores count of max occurring element max_so_far = - 323567 # traverse each pair in map and find maximum # occurring element and its frequency for p in mp : if ( mp [ p ] > max_so_far ): max_so_far = mp [ p ] max_element = p # generate a random number between [1 max_so_far] r = int ( (( random . randrange ( 1 max_so_far 2 ) % max_so_far ) + 1 )) i = 0 count = 0 # traverse array again and return index of rth # occurrence of max element while ( i < n ): if ( arr [ i ] == max_element ): count = count + 1 # Print index of rth occurrence of max element if ( count == r ): print ( 'Element with maximum frequency present at index ' i ) break i = i + 1 # Driver code # input array arr = [ - 1 4 9 7 7 2 7 3 0 9 6 5 7 8 9 ] n = len ( arr ) findRandomIndexOfMax ( arr n ) # This code is contributed by Arnab Kundu
C# using System ; using System.Collections.Generic ; class GFG { // Function to return index of most occurring element // of the array randomly with equal probability static void findRandomIndexOfMax ( int [] arr int n ) { // freq store frequency of each element in the array Dictionary < int int > mp = new Dictionary < int int > (); for ( int i = 0 ; i < n ; i ++ ) { if ( mp . ContainsKey ( arr [ i ])) { mp [ arr [ i ]] ++ ; } else { mp [ arr [ i ]] = 1 ; } } int max_element = int . MinValue ; // stores max occurring element // stores count of max occurring element int max_so_far = int . MinValue ; // traverse each pair in map and find maximum // occurring element and its frequency foreach ( KeyValuePair < int int > p in mp ) { if ( p . Value > max_so_far ) { max_so_far = p . Value ; max_element = p . Key ; } } // generate a random number between [1 max_so_far] Random rand = new Random (); int r = rand . Next ( max_so_far ) + 1 ; // traverse array again and return index of rth // occurrence of max element for ( int i = 0 count = 0 ; i < n ; i ++ ) { if ( arr [ i ] == max_element ) count ++ ; // print index of rth occurrence of max element if ( count == r ) { Console . WriteLine ( 'Element with maximum frequency present ' + 'at index ' + i + 'n' ); break ; } } } // Driver code public static void Main () { // input array int [] arr = { - 1 4 9 7 7 2 7 3 0 9 6 5 7 8 9 }; int n = arr . Length ; findRandomIndexOfMax ( arr n ); } }
JavaScript < script > // Javascript program to return index of most occurring element // of the array randomly with equal probability // Function to return index of most occurring element // of the array randomly with equal probability function findRandomIndexOfMax ( arr n ) { // freq store frequency of each element in the array let mp = new Map (); for ( let i = 0 ; i < n ; i ++ ) if ( mp . has ( arr [ i ])) { mp . set ( arr [ i ] mp . get ( arr [ i ]) + 1 ); } else { mp . set ( arr [ i ] 1 ); } let max_element = Number . MIN_VALUE ; // stores max occurring element // stores count of max occurring element let max_so_far = Number . MIN_VALUE ; // traverse each pair in map and find maximum // occurring element and its frequency for ( let [ key value ] of mp . entries ()) { if ( value > max_so_far ) { max_so_far = value ; max_element = key ; } } // generate a random number between [1 max_so_far] let r = Math . floor ((( Math . random () * max_so_far ) % max_so_far ) + 1 ) // traverse array again and return index of rth // occurrence of max element for ( let i = 0 count = 0 ; i < n ; i ++ ) { if ( arr [ i ] == max_element ) count ++ ; // print index of rth occurrence of max element if ( count == r ) { document . write ( 'Element with maximum frequency present ' + 'at index ' + i + '
' ); break ; } } } // Driver code let arr = [ - 1 4 9 7 7 2 7 3 0 9 6 5 7 8 9 ]; let n = arr . length ; findRandomIndexOfMax ( arr n ); // This code is contributed by avanitrachhadiya2155 < /script>
Sortir:
Element with maximum frequency present at index 4
Complexité temporelle de la solution ci-dessus est O(n).
Espace auxiliaire utilisé par le programme est O(n).
