Максимальная частота любого элемента массива, возможная не более чем на K приращений

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

Примеры:

Input: arr[] = {1, 4, 8, 13}, N = 4, K = 5 
Output: 2 
Explanation: 
Incrementing arr[0] twice modifies arr[] to {4, 4, 8, 13}. Maximum frequency = 2. 
Incrementing arr[1] four times modifies arr[] to {1, 8, 8, 13}. Maximum frequency = 2. 
Incrementing arr[2] five times modifies arr[] to {1, 4, 13, 13}. Maximum frequency = 2. 
Therefore, the maximum possible frequency of any array element that can be obtained by at most 5 increments is 2.

Input: arr[] = {2, 4, 5}, N = 3, K = 4 
Output: 3

Подход: Эту проблему можно решить с помощью метода скользящего окна и сортировки. Следуйте инструкциям, чтобы решить эту проблему.

• Отсортируйте массив arr[] .
• Инициализируйте переменные sum = 0, start = 0 и результирующая частота res = 0 .
• Пройдите массив по диапазону индексов [0, N – 1] и выполните следующие шаги:
  • Увеличить сумму на arr[end] .
  • Повторяйте цикл до тех пор, пока значение [(end – start + 1) * arr[end] – sum] не станет меньше K , и выполните следующие операции:
    • Уменьшите значение суммы на arr[start] .
    • Увеличьте значение start на 1 .
  • После выполнения вышеуказанных шагов все элементы в диапазоне [начало, конец] можно сделать равными, используя не более K операций. Поэтому обновите значение res как максимальное res и (конец — начало + 1).
• Наконец, выведите значение res как частоту наиболее часто встречающегося элемента после выполнения K операций.

Ниже приведена реализация вышеуказанного подхода:

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