Сортировать числовую строку, заданную как массив, перемещая элемент с индексом i на i шагов вправо

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

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

Note: In a step, two numbers can lie in the same position.

Примеры:

Input: N = 4, arr[] = {1, 2, 7, 4}
Output: 1
Explanation: Moving the element at index 3 by 2 steps to the right sorts the array in ascending order in 1 move. Therefore, print 1.

Input: N = 5, arr[] = {2, 5, 8, 1, 9}
Output: 12
Explanation:
The most optimal way to arrange the array is: arr[] = {-, -, -, 1, -, -, -,2, -, -, -, -, -, -, -, 5, -, -, -, -, -, -, -, 8, -, -, -, -, -, -, -, -, -, -, -, -,-, -, -, 20}

  1. First arr[0] jumps to index 2, then to index 4, and then to index 7. So Shifting arr[0] will need 3 moves to reach index 7. 
  2. First arr[1] jumps to index 3, then to index 7, and then to index 15. So Shifting arr[1] will need 3 moves to reach index 15. 
  3. First arr[2] jumps to index 6, then to index 12, and then to index 24. So Shifting arr[2] will need 3 moves to reach index 23.
  4. First arr[4] jumps to index 9, then to index 19, and then to index 39. So Shifting arr[4] will also need 3 moves to reach index 39.

Therefore, the total of (3 + 3 + 3 + 3) = 12 moves is needed.

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

  • Инициализируйте карту, скажем M , которая хранит элементы массива с их индексом в данном массиве arr[] .
  • Пройдите по заданному массиву arr[] с помощью переменной i и обновите карту M[arr[i]] как M[arr[i]] = (i + 1) .
  • Инициализируйте переменную, скажем , как 0 , которая хранит минимальное количество необходимых ходов.
  • Перейдите карту M и выполните следующие шаги:
    • Сохраните позицию текущего итератора и предыдущего итератора в переменных, скажем, i и j .
    • Итерировать до тех пор, пока i->second не станет меньше или равно j->second и увеличить значение ans на 1 и увеличить значение i->second на i->second .
  • После выполнения вышеуказанных шагов выведите значение ans как результирующее минимальное количество ходов.

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


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

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