Максимизируйте количество элементов, которые строго больше в подпоследовательности, чем их среднее значение

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

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

Пример:

Input: arr[] = {1, 1, 3, 2, 4}
Output: 3
Explanation:
Operation 1: Choose the subsequence {1, 2, 4}, average = (1+2+4)/3 = 2. So arr[5]=4 is deleted. arr[]={1, 1, 3, 2}
Operation 2: Choose the subsequence {1, 3, 2}, average = (1+3+2)/3 = 2. So arr[2]=3 is deleted. arr[]={1, 1, 2}
Operation 3: Choose the subsequence {1, 1}, average = (1+1)/2 = 1. So arr[3]=2 is deleted. arr[]={1, 1}
No further deletions can be performed.

Input: arr[] = {5, 5, 5}
Output: 0

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

  1. Найдите частоту минимального элемента, скажем freq .
  2. Возвратите N-freq как ответ на эту проблему.

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


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

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