Сведите к минимуму максимальную частоту элементов массива, заменив их только один раз
Опубликовано: 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 freqM 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)