Максимизировать частоту элемента не более чем на одно увеличение или уменьшение всех элементов массива | Набор 2

Опубликовано: 21 Сентября, 2022

Учитывая массив arr[] размера N , задача состоит в том, чтобы найти максимальную частоту любого элемента массива, увеличивая или уменьшая каждый элемент массива на 1 не более одного раза.

Примеры:

Input: arr[] = { 3, 1, 4, 1, 5, 9, 2 } 
Output: 4 
Explanation: 
Decrementing the value of arr[0] by 1 modifies arr[] to { 2, 1, 4, 1, 5, 9, 2 } 
Incrementing the value of arr[1] by 1 modifies arr[] to { 2, 2, 4, 1, 5, 9, 2 } 
Incrementing the value of arr[3] by 1 modifies arr[] to { 2, 2, 4, 1, 5, 9, 2 } 
Therefore, the frequency of an array element(arr[0]) is 4 which is the maximum possible.

Input: arr[] = { 0, 1, 2, 3, 4, 5, 6 } 
Output: 3 
Explanation: 
Incrementing the value of arr[0] by 1 modifies arr[] to { 1, 1, 2, 3, 4, 5, 6 } 
Decrementing the value of arr[2] by 1 modifies arr[] to { 1, 1, 1, 3, 4, 5, 6 } 
Therefore, the frequency of an array element(arr[0]) is 3 which is the maximum possible.

Жадный подход: жадный подход к решению этой проблемы обсуждался в наборе 1 этой статьи.

Подход с подсчетом частоты: Идея состоит в том, чтобы создать массив частот и сохранить частоты всех элементов массива arr[i]. Теперь для каждого возможного значения элемента попробуйте объединить левое и правое значения в эту точку, т.е. freq[i] + freq[i-1] + freq[i+1]. Выполните следующие шаги, чтобы решить проблему:

  • Определите переменную MAXN со значением 1e5.
  • Инициализировать массив freq[MAXN] со значениями 0.
  • Перебрать диапазон [0, N), используя переменную i , и выполнить следующие задачи:
    • Увеличьте значение freq[arr[i]] на 1.
  • Инициализируйте переменную max_freq со значением -MAXN.
  • Перебрать диапазон [1, MAXN-1), используя переменную i , и выполнить следующие задачи:
    • Установите значение max_freq как максимальное значение max_freq или freq[i-1] + freq[i] + freq[i+1].
  • После выполнения вышеуказанных шагов выведите значение max_freq в качестве ответа.

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


Временная сложность: O(N)
Вспомогательное пространство: O(|Max|), где Max — максимальный элемент в массиве.

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