Отсортируйте массив с одним неуместным числом, поменяв местами элементы любое количество раз

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

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

Примеры:

Input : N = 7, pos = 6, arr = {1, 2, 3, 4, 9, 15, 0}
Output: 0 1 2 3 4 9 15
Explanation:
Applying following swap arr can be sorted:

1. swap element 0 and 1, Now arr is {0, 2, 3, 4, 9, 15, 1}
2. swap element 1 and 2, Now arr is {0, 1, 3, 4, 9, 15, 2}
3. swap element 2 and 3, Now arr is {0, 1, 2, 4, 9, 15, 3}
4. swap element 3 and 4, Now arr is {0, 1, 2, 3, 9, 15, 4}
5. swap element 4 and 9, Now arr is {0, 1, 2, 3, 4, 15, 9}
6. swap element 9 and 15, Now arr is {0, 1, 2, 3, 4, 9, 15}

We can see now, the array arr[ ] has been sorted.

Input: N = 4, pos = 2, arr = {2, 3, 1, 4, }
Output: 1 2 3 4

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

  • Пройдите массив arr[ ] , если элемент слева от pos arr[i] больше, чем arr[pos] , поменяйте местами arr[i] и arr[pos] .
  • Если элемент справа от pos arr[j] меньше, чем arr[pos] , поменяйте местами arr[j] и arr[pos] .
  • Печать arr[ ] будет последним шагом.

Ниже приведена реализация описанного выше подхода.


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

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