Измените массив, удалив M наименьших элементов, сохраняя порядок оставшихся элементов.

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

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

Примеры:

Input: M = 5, arr[] = {2, 81, 75, 98, 72, 63, 53, 5, 40, 92} 
Output: 81 75 98 72 92
Explanation:
The first M(= 5) smallest element are {2, 5, 40, 53, 63}. After removing these elements the modified array is {81, 75, 98, 72, 92}.

Input: M = 1, arr[] = {8, 3, 6, 10, 5}
Output: 8 6 10 5

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

  • Инициализируйте вектор пар A и инициализируйте A[i] как {arr[i], i} .
  • Отсортируйте вектор A[]по первому элементу пары.
  • Отсортируйте элементы в диапазоне [M, N – 1] по второму элементу пары.
  • Теперь выполните итерацию по заданному диапазону [M, N – 1], используя переменную i , и напечатайте значение A[i].first в качестве результирующего элемента массива.

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

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

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

  • Инициализируйте вспомогательный вектор, скажем, A , и сохраните в нем все элементы массива arr[] .
  • Отсортируйте вектор A и инициализируйте HashMap, скажем, mp .
  • Переберите диапазон [0, M – 1] , используя переменную i , и вставьте A[i] в HashMap.
  • Переберите диапазон [0, N – 1] , используя переменную i , и, если значение arr[i] отсутствует в HashMap, выведите значение arr[i] в качестве результирующего массива.

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

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

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