Encuentre un índice del elemento máximo que ocurre con la misma probabilidad

Dada una array de enteros, encuentre el elemento que aparece más en la array y devuelva cualquiera de sus índices aleatoriamente con la misma probabilidad.
Ejemplos: 
 

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.

La idea es iterar a través de la array una vez y encontrar el elemento máximo que aparece y su frecuencia n. Luego generamos un número aleatorio r entre 1 y n y finalmente devolvemos la r’ésima ocurrencia del elemento máximo que ocurre en la array.
A continuación se muestra la implementación de la idea anterior: 
 

// C++ program to return index of most occurring element
// of the array randomly with equal probability
#include <iostream>
#include <unordered_map>
#include <climits>
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 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 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

<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 +"<br>");
            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>

Producción: 
 

Element with maximum frequency present at index 4

La complejidad temporal de la solución anterior es O(n). 
El espacio auxiliar utilizado por el programa es O(n).
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.