logo

TechCodeview

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++ 
// 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(arrn) {  // 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).