Минимальные замены с 0 для сортировки массива

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

Примеры:

Input: N = 5, A[] = {2, 2, 1, 1, 3}
Output: 1
Explanation: We choose X = 2 and replace all the occurrences of 2 with 0. Now the array becomes {2, 2, 1, 1, 3} -> {0, 0, 1, 1, 3} , which is sorted in increasing order.

Input: N = 4, A[] = {2, 4, 1, 2}
Output: 3

Подход: Проблема может быть легко решена с помощью Карты.

Наблюдения:

There are 2 cases that need to be considered :

• Case 1: Same element occurs more than once non-contiguously 
  • Consider the array : {1,6,3,4,5,3,2}. 
  • Now, since 3 at index 5 is greater than its next element, so we will make that 0 (as well as 3 at index 2). 
  • The array becomes {1,6,0,4,5,0,2}. 
  • So, the only way to sort the array would be to make all the elements before the zeroes equal to 0. i.e. the array becomes {0,0,0,0,0,0,2}.
• Case 2: Element at ith index is greater than the element at (i+1)th index :
  • Consider the array : {1,2,3,5,4}. 
  • Since the element at the 3rd index is greater than the element at 4th index, we have to make the element at 3rd index equal to zero. 
  • So , the array becomes {1,2,3,0,4}. 
  • Now, the only way to sort the array would be to make all the elements before the zero equal to 0. i.e. the array becomes {0,0,0,0,4}.

It can be observed that in the end Case 2 breaks down to Case 1.

Учитывая вышеперечисленные случаи, проблему можно решить, выполнив следующие шаги:

• Объявите хэш-карту и добавьте в карту частоту каждого элемента массива.
• Перебрать массив с конца, т.е. от i=N-1 до i=0.
• На каждой итерации обрабатывайте случаи 1 и 2, как описано выше.
• Если итерация завершена, вернуть 0.

Ниже приведена реализация этого подхода:

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