#algorithm #sorting #permutation #mergesort
Вопрос:
Вопрос:
Заданный массив из N чисел содержит перестановку N. У вас есть 2 типа свопов:
- Поменяйте местами любые 2 номера массива (вы можете сделать это только один раз)
- Поменяйте местами соседние номера (вы можете сделать это много раз)
Какое наименьшее количество подкачек для сортировки массива?
Пример:
arr[] = {5, 3, 4, 2, 1}
answer: 3
Explaination:
- Swap 5 and 1
- Swap 4 and 2
- Swap 3 and 2
П/С:
Я думаю, что сначала нам нужно использовать «свободный обмен», а затем использовать сортировку слиянием. Но я не знаю, как использовать «свободный обмен», чтобы сортировка слиянием была минимальной.
Комментарии:
1. Вы имели в виду пузырьковый сорт?
2. Я бы использовал свободный обмен на 2 числа, которые являются дальнейшими.
3. @Tarik но иногда это не оптимальный способ
4. Сортировка пузырьков @Tarik может иметь много «бесплатных свопов», это может быть только один, а остальные соседние свопы
5. может ли массив содержать только от 1 до N чисел?
Ответ №1:
Я думаю, вы можете просто поменять номер, который находится слева от того места, где он должен быть, на тот, который находится справа от того места, где он должен быть.
Таким образом, слева будет индекс i, где arr[i] — i является максимальным. И справа будет индекс j, где arr[j] — j-минимум. Затем просто замените элемент i на j. Это O(n).
После этого вы можете подсчитать количество свопов, которые вам нужно сделать для сортировки пузырьков. Для этого вы подсчитываете все элементы, которые меньше и находятся справа от текущего элемента. Вы можете сделать это в O(n logn), перейдя справа налево, а затем для каждого элемента вы вставляете его в сбалансированное отсортированное дерево, где вы также сохраняете количество узлов в поддереве для каждого ребра (например, модифицированное дерево AVL). Это позволяет вам подсчитать количество элементов, которые меньше и справа от текущего в O(logn).