Keresse meg a maximálisan előforduló elem indexét azonos valószínűséggel
Adott egész számok tömbje keresse meg a tömb leggyakrabban előforduló elemét, és adja vissza bármelyik indexét véletlenszerűen, azonos valószínűséggel.
Példák:
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.
Az ötlet az, hogy egyszer végigiteráljuk a tömböt, és megtudjuk a maximálisan előforduló elemet és annak n gyakoriságát. Ezután generálunk egy r véletlenszerű számot 1 és n között, és végül visszaadjuk a tömbben a maximálisan előforduló elem r'-edik előfordulását.
Alább látható a fenti ötlet megvalósítása -
// 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>
Kimenet:
Element with maximum frequency present at index 4
Időbeli összetettség a fenti megoldás O(n).
Segédtér a program által használt O(n).
