Постановка задачи

Всякий раз, когда Джордж просит Лили потусоваться, она занята домашним заданием. Джордж хочет помочь ей закончить быстрее, но у него не получается! Поможешь Джорджу понять домашнее задание Лили, чтобы она могла проводить с ним время?

Рассмотрим массив из n различных целых чисел, arr= [a[0], a[1],…,a[n-1]] . Джордж может поменять местами любые два элемента массива любое количество раз. Массив красив, если сумма |a[i] — a[i-1]| среди 0 ‹ i ‹ n минимален.

Учитывая массив arr, определите и верните минимальное количество обменов, которое необходимо выполнить, чтобы сделать массив красивым.

Соображения

Давайте не будем отвлекаться на несущественные детали, а попробуем найти, в чем проблема, и сосредоточим на ней все безраздельное внимание.

Задача на минимальное количество свопов для сортировки массива – это алгоритмическая задача, которая требует минимального количества свопов, необходимых для сортировки массива элементов.

Свопы

Обмен — это операция, которая меняет местами два элемента в массиве.

Графики

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

Цикл

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

Алгоритм

Алгоритм основан на Амиле Рукшан, но немного отклоняется, чтобы сделать алгоритм ясным и лаконичным.

  1. Функция lilysHomework сначала определяет две функции: ascendingOrder и descendingOrder. Эти функции используются для сортировки массива по возрастанию и убыванию соответственно.
  2. Затем функция дважды вызывает функцию calculateSwaps, один раз с массивом, отсортированным по возрастанию, и один раз с массивом, отсортированным по убыванию.
  3. Функция calculateSwaps принимает два аргумента: массив для сортировки и функцию сортировки. Сначала функция делает копию массива.
  4. Затем функция сортирует копию массива с помощью функции сортировки.
  5. Затем функция создает карту, которая сопоставляет каждый элемент массива с его правильной позицией.
  6. Затем функция создает массив логических значений, где каждое значение указывает, был ли посещен соответствующий элемент в массиве.
  7. Затем функция перебирает исходный массив.
  8. Для каждого элемента массива функция проверяет, посещался ли элемент. Если элемент не был посещен, функция запускает цикл.
  9. Функция перебирает массив, пока не найдет посещенный элемент. Для каждого элемента в цикле функция помечает элемент как посещенный и увеличивает размер цикла.
  10. Когда функция достигает посещенного элемента, она останавливает цикл и добавляет размер цикла к количеству свопов.
  11. Функция возвращает количество свопов.

Ресурсы

Беседа Google Bard помогла мне написать и дала набросок, чтобы собрать воедино мои идеи