Это вопрос интервью. swap означает удаление любого элемента из массива и добавление его в конец того же массива. Учитывая массив целых чисел, найдите минимальное количество swaps необходимое для сортировки массива.
Есть ли решение лучше, чем O(n^2)?
Например:
Входной массив: [3124].
Количество swaps: 2 ([3124] → [1243] → [1234]).
Это может работать в O(nlogn), даже если мы не принимаем массив последовательных значений.
Если мы это сделаем - это можно сделать в O(n).
Один из способов сделать это - с O(n) пробелом и временем O(nlogn).
Данный массив A сортирует его (O(nlogn)) во второй массив B.
теперь... (массивы индексируются из 1)
swaps = 0
b = 1
for a = 1 to len(A)
if A[a] == B[b]
b = b + 1
else
swaps = swaps + 1
Проблема сводится к поиску самого длинного префикса отсортированного массива, который появляется как подпоследовательность во входном массиве. Это определяет элементы, которые не нужно сортировать. Остальные элементы нужно будет удалять один за другим, от самого маленького до самого большого и прилагаться сзади.
В вашем примере [3, 1, 2, 4] уже отсортированная подпоследовательность [1, 2]. Оптимальное решение - удалить оставшиеся два элемента, 3 и 4, и добавить их обратно. Таким образом, оптимальным решением является два "свопа".
Поиск подпоследовательности можно выполнить в O(n logn) с использованием O(n) дополнительной памяти. Следующий псевдокод сделает это (код также является действительным Python):
l = [1, 2, 4, 3, 99, 98, 7]
s = sorted(l)
si = 0
for item in l:
if item == s[si]:
si += 1
print len(l) - si
Если, как в вашем примере, массив содержит перестановку целых чисел от 1 до n, проблема может быть решена в O(n) с использованием O(1) памяти:
l = [1, 2, 3, 5, 4, 6]
s = 1
for item in l:
if item == s:
s += 1
print len(l) - s + 1
В более общем плане второй метод может использоваться всякий раз, когда мы знаем выходный массив априори и, следовательно, его не нужно искать путем сортировки.
Наблюдение: если элемент заменен на спину, его предыдущая позиция не имеет значения. Ни один элемент не должен меняться местами более одного раза.
Наблюдение: последний обмен (если есть) должен перемещать самый большой элемент.
Наблюдение: перед свопом массив (исключая последний элемент) должен быть отсортирован (по прежним свопам или изначально)
Алгоритм сортировки, предполагая, что значения являются последовательными: найдите самую длинную отсортированную подпоследовательность последовательных (по значению) элементов, начиная с 1:
3 1 5 2 4
поменяйте все более высокие элементы по очереди:
1 5 2 4 3
1 5 2 3 4
1 2 3 4 5
Чтобы найти количество свопов в O (n), найдите длину самой длинной отсортированной подпоследовательности последовательных элементов, начиная с 1:
то количество свопов = длина ввода - самая длинная отсортированная подпоследовательность.
Альтернативное решение (O (n ^ 2)), если вход не является перестановкой 1..n:
Еще одно решение (O (n log n)), предполагающее уникальные элементы:
Если вы не хотите копировать входной массив, сортируйте по oldPos до последнего шага.
Это можно сделать в O (n log n).
Сначала найдите минимальный элемент в массиве. Теперь найдите элемент max, который встречается перед этим элементом. Назовите это max_left. Вы должны вызвать swap() для всех элементов перед элементом min массива.
Теперь найдите самую длинную возрастающую подпоследовательность справа от элемента min вместе с ограничением, что вы должны пропустить элементы, значения которых больше max_left.
Требуемое количество свопов - size(array) - size(LIS).
Например, рассмотрим массив,
7 8 9 1 2 5 11 18
Минимальный элемент в массиве равен 1. Таким образом, мы находим max до минимального элемента.
7 8 9 | 1 2 5 11 18
max_left = 9
Теперь найдите LIS справа от минимума с элементами < 9 LIS = 1,2,5
Нет свопов = 8 - 3 = 5
В тех случаях, когда max-элемент равен null, т.е. min - это первый элемент, найдите LIS массива и требуемый ответ - size (array) -size (LIS)
Пример
2 5 4 3
max_left имеет значение null. LIS 2 3
Нет свопов = размер (массив) - размер (LIS) = 4 - 2 = 2
Вот код в Python для минимального количества перестановок,
def find_cycles(array):
cycles = []
remaining = set(array)
while remaining:
j = i = remaining.pop()
cycle = [i]
while True:
j = array[j]
if j == i:
break
array.append(j)
remaining.remove(j)
cycles.append(cycle)
return cycles
def minimum_swaps(seq):
return sum(len(cycle) - 1 for cycle in find_cycles(seq))
@all, принятое решение, предоставляемое @Itay karo и @NPE, совершенно неверно, потому что оно не учитывает будущий порядок смены элементов...
Он терпит неудачу для многих тестовых примеров, таких как:
3 1 2 5 4
правильный вывод: 4
но их коды дают результат как 3...
: 3 1 2 5 4 --- > 1 2 5 4 3 --- > 1 2 4 3 5 --- > 1 2 3 5 4 --- > 1 2 3 4 5
PS: я не могу комментировать там из-за низкой репутации
int numSwaps(int arr[], int length) {
bool sorted = false;
int swaps = 0;
while(!sorted) {
int inversions = 0;
int t1pos,t2pos,t3pos,t4pos = 0;
for (int i = 1;i < length; ++i)
{
if(arr[i] < arr[i-1]){
if(inversions){
tie(t3pos,t4pos) = make_tuple(i-1, i);
}
else tie(t1pos, t2pos) = make_tuple(i-1, i);
inversions++;
}
if(inversions == 2)
break;
}
if(!inversions){
sorted = true;
}
else if(inversions == 1) {
swaps++;
int temp = arr[t2pos];
arr[t2pos] = arr[t1pos];
arr[t1pos] = temp;
}
else{
swaps++;
if(arr[t4pos] < arr[t2pos]){
int temp = arr[t1pos];
arr[t1pos] = arr[t4pos];
arr[t4pos] = temp;
}
else{
int temp = arr[t2pos];
arr[t2pos] = arr[t1pos];
arr[t1pos] = temp;
}
}
}
return swaps;
}
Этот код возвращает минимальное количество свопов, необходимых для сортировки массива inplace.
Например, A [] = [7,3,4,1] Поменяв 1 и 7, получим [1,3,4,7]. аналогично B [] = [1,2,6,4,8,7,9]. Сначала мы заменим 6 на 4, поэтому B [] → [1,2,4,6,8,7,9]. Тогда 7 с 8. So → [1,2,4,6,7,8,9]
Алгоритм работает в O (количество пар, где значение в индексе я < значение при индексе i-1) ~ O (N).
Написание очень простой JavaScript-программы для сортировки массива и определения количества перестановок:
function findSwaps(){
let arr = [4, 3, 1, 2];
let swap = 0
var n = arr.length
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j]
swap = swap + 1
}
}
}
console.log(arr);
console.log(swap)
}
Слушайте, мое решение в С# для решения минимального числа перестановок, необходимых для короткого массива. В то время мы можем поменять местами только 2 элемента (в любой позиции индекса).
public class MinimumSwaps2
{
public static void minimumSwapsMain(int[] arr)
{
Dictionary<int, int> dic = new Dictionary<int, int>();
Dictionary<int, int> reverseDIc = new Dictionary<int, int>();
int temp = 0;
int indx = 0;
//find the maximum number from the array
int maxno = FindMaxNo(arr);
if (maxno == arr.Length)
{
for (int i = 1; i <= arr.Length; i++)
{
dic[i] = arr[indx];
reverseDIc.Add(arr[indx], i);
indx++;
}
}
else
{
for (int i = 1; i <= arr.Length; i++)
{
if (arr.Contains(i))
{
dic[i] = arr[indx];
reverseDIc.Add(arr[indx], i);
indx++;
}
}
}
int counter = FindMinSwaps(dic, reverseDIc, maxno);
}
static int FindMaxNo(int[] arr)
{
int maxNO = 0;
for (int i = 0; i < arr.Length; i++)
{
if (maxNO < arr[i])
{
maxNO = arr[i];
}
}
return maxNO;
}
static int FindMinSwaps(Dictionary<int, int> dic, Dictionary<int, int> reverseDIc, int maxno)
{
int counter = 0;
int temp = 0;
for (int i = 1; i <= maxno; i++)
{
if (dic.ContainsKey(i))
{
if (dic[i] != i)
{
counter++;
var myKey1 = reverseDIc[i];
temp = dic[i];
dic[i] = dic[myKey1];
dic[myKey1] = temp;
reverseDIc[temp] = reverseDIc[i];
reverseDIc[i] = i;
}
}
}
return counter;
}
}
for(int count = 1; count<=length; count++)
{
tempSwap=0; //it will count swaps per iteration
for(int i=0; i<length-1; i++)
if(a[i]>a[i+1])
{
swap(a[i],a[i+1]);
tempSwap++;
}
if(tempSwap!=0) //check if array is already sorted!
swap += tempSwap;
else
break;
}
System.out.println(swaps);
это решение O (n), которое работает для всех входов:
static int minimumSwaps(int[] arr) {
int swap=0;
boolean visited[]=new boolean[arr.length];
for(int i=0;i<arr.length;i++){
int j=i,cycle=0;
while(!visited[j]){
visited[j]=true;
j=arr[j]-1;
cycle++;
}
if(cycle!=0)
swap+=cycle-1;
}
return swap;
}
}
def minimumSwaps(arr):
swaps = 0
'''
first sort the given array to determine the correct indexes
of its elements
'''
temp = sorted(arr)
# compare unsorted array with the sorted one
for i in range(len(arr)):
'''
if ith element in the given array is not at the correct index
then swap it with the correct index, since we know the correct
index because of sorting.
'''
if arr[i] != temp[i]:
swaps += 1
a = arr[i]
arr[arr.index(temp[i])] = a
arr[i] = temp[i]
return swaps
@NPE: ваше решение O (n) не выполнено для: {4,3,1,2}, так как S будет 1 len: 4, возврат: 4-1-1: 2, хотя решение - 3.
int temp = 0, swaps = 0;
for (int i = 0; i < arr.length;) {
if (arr[i] != i + 1){
// System.out.println("Swapping --"+arr[arr[i] - 1] +" AND -- "+arr[i]);
temp = arr[arr[i] - 1];
arr[arr[i] - 1] = arr[i];
arr[i] = temp;
++swaps;
} else
++i;
// System.out.println("value at position -- "+ i +" is set to -- "+ arr[i]);
}
return swaps;
Это самый оптимизированный ответ, который я нашел. Это так просто. Вы, вероятно, поймете в один взгляд через цикл. Благодаря Дэррилу в ранге хакера.