Сведите к минимуму максимальную частоту элементов массива, заменив их только один раз

Опубликовано: 26 Февраля, 2023

Учитывая массив A[] длины N, задача состоит в том, чтобы минимизировать максимальную частоту любого элемента массива, выполнив следующую операцию только один раз:

  • Выберите любой случайный набор (скажем, S ) индексов i (0 ≤ i ≤ N-1 ) массива так, чтобы все элементы S были одинаковыми и
  • Замените каждый элемент этого индекса любым другим числом.

Примеры:

Input: A[] = {1 ,4 ,4 ,1 ,4 , 4} 
Output: 2
Explanation: Choose index i = {1, 2} and perform the operation 
{ 1, 4, 4, 1, 4, 4 }→ { 1, 5, 5, 1, 4, 4 }. 
The highest frequency is of element 4, 5 and 1 which is 2
This is the minimum possible value of highest frequency of an element.

Input: A[] = {5 ,5 ,5 ,5 ,5 } 
Output: 3

Подход: Задача может быть решена на основе следующего наблюдения:

  • Let N be the element with the maximum frequency in A[] and M be the element with the second maximum frequency in A[]. It is possible that M does not exist.
  • If M exist then maximum frequency = freqN
    • Indices such that A[i] = N, should be chosen because the final value of freqN should be minimized and it is always better to replace with number(num) such that num ≠ M. Only a maximum of ⌊ freqN/2⌋ elements should be replaced because if we replace more, then num becomes the new element with the maximum frequency
    • Hence, it is optimal to replace ⌊ freqN/2⌋  occurrences of N to some num ≠ M.Now, freqN – ⌊ freqN/2⌋ is the final frequency of N and freq is the final frequency of M. 
    • The maximum among these two i.e. Max( freqN – ⌊ freqN/2⌋, freqM ) has to be the answer because the frequency of num = ⌊freqN/2⌋ ≤( freqN – ⌊ freqN/2⌋) = frequency of N .
  • If M does not exist it means freqM = 0 . So , the answer is freqN – ⌊ freqN/2⌋.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

  • Найдите частоту наиболее часто встречающегося и второго по частоте элемента.
  • Сравните эти частоты.
    • Основываясь на частоте, следуйте приведенным выше условиям, чтобы найти минимальное значение максимальной частоты.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * logN)
Вспомогательное пространство: O(N)

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