Найдите индекс максимального встречающегося элемента с равной вероятностью

Опубликовано: 20 Января, 2022

Для массива целых чисел найдите наиболее часто встречающийся элемент массива и верните любой из его индексов случайным образом с равной вероятностью.

Примеры:

Вход:
arr [] = [-1, 4, 9, 7, 7, 2, 7, 3, 0, 9, 6, 5, 7, 8, 9]

Выход: 
Элемент с максимальной частотой присутствует в индексе 6
ИЛИ
Элемент с максимальной частотой присутствует в индексе 3
ИЛИ
Элемент с максимальной частотой присутствует в индексе 4
ИЛИ
Элемент с максимальной частотой присутствует в индексе 12

Все вышеперечисленные выходы имеют равную вероятность.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Идея состоит в том, чтобы выполнить итерацию по массиву один раз и определить максимальный элемент и его частоту n. Затем мы генерируем случайное число r между 1 и n и, наконец, возвращаем r-е вхождение максимального встречающегося элемента в массиве.

Below are implementation of above idea –

C++

// 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

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

Выход:

Элемент с максимальной частотой присутствует в индексе 4

Временная сложность вышеприведенного решения составляет O (n ).
Вспомогательное пространство, используемое программой, равно O (n).

Эта статья предоставлена Адитьей Гоэлем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ