Минимальное количество переходов, необходимое для сортировки чисел, расположенных на числовой строке

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

Даны два массива W[] и L[] , состоящие из N положительных целых чисел, где W[i] изначально находится в позиции i на бесконечной числовой строке. При каждом прыжке вперед W[i] может перейти на позицию (j + L[i]) из текущей позиции j в любую вакантную позицию. Задача состоит в том, чтобы найти минимальное количество прыжков вперед, необходимое для сортировки массива.

Примеры:

Input: W[] = {2, 1, 4, 3}, L[] = {4, 1, 2, 4}
Output: 5
Explanation:
Initially, 2 is at position 0, 1 is at position 1, 4 is at position 2, 3 is at position 3 on the number line as: 2 1 4 3
Push number 2 to jump from its current position 0 to position 4, arrangement on the number line: _ 1 4 3 2
Push number 3 to jump from its current position 3 to position 7, arrangement on the number line: _ 1 4 _ 2 _ _ 3
Push number 4 to jump from its current position 2 to position 8, arrangement on the number line: _ 1 _ _ 2 _ _ 3 4

Therefore, the total number of jumps required is 1 + 1 + 3 = 5.

Input: W[] = {3, 1, 2}, L[] = {1, 4, 5}
Output: 3

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

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

  • Инициализируйте переменную, скажем , как 0 , чтобы сохранить минимальное количество необходимых переходов.
  • Создайте копию массива W[] и сохраните элементы в отсортированном порядке в массиве arr[] .
  • Инициализируйте HashMap pos , в котором хранится текущая позиция элемента W[i] .
  • Пройдите массив W[] и обновите позицию W[i] в pos .
  • Пройдите массив arr[] в диапазоне [1, N – 1] и выполните следующие шаги:
    • Сохраните позицию arr[i] и позицию arr[i – 1] в массиве W[] в переменных, скажем, curr и prev соответственно.
    • Если значение curr больше, чем prev , то переходите к следующей итерации.
    • В противном случае итерируйте до тех пор, пока curr ≤ prev или curr уже не будет занято, и увеличьте значение curr на скачок и увеличьте значение ans на 1 .
    • Обновите позицию arr[i] в HashMap pos на curr .
  • После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

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

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

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