Минимизируйте вставки или удаления, чтобы частота каждого элемента массива равнялась его значению.

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

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

Пример:

Input: arr = {3, 2, 3, 1, 2}
Output: 1
Explanation: Initially, the frequency of integers in the array is freq[3] = 2, freq[2]  = 2 and freq[1] = 1. In the 1st operation, insert 3 into the array. Hence the array becomes arr[] = {3, 2, 3, 1, 2, 3} having frequency of each element equal to its value. 

Input: [3, 3, 4, 3, 1, 2]
Output: 2
Explanation: In 1st operation, delete 4 from the array. In 2nd operation, insert 2 into the array. Hence the array becomes arr[] = {3, 3, 3, 1, 2, 2} having frequency of each element equal to its value.  

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

  • Создайте хэш-карту freq для хранения частоты всех элементов массива.
  • Перебрать все значения карты, используя ключ переменной. Если freq[key] > key , она будет способствовать (freq[key] – key) общему количеству операций, в противном случае она будет способствовать min(freq[key], key – freq[key]) в общем количестве операций.
  • Создайте переменную count , в которой хранится количество операций всех возможных значений ключа, которые будут требуемым ответом.

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

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

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