Измените массив, удалив M наименьших элементов, сохраняя порядок оставшихся элементов.
Для данного положительного целого числа 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)