Judgecode - Сортировка с заменой (2)

Question

Проблема, которую я видел, такая же ребята, у кого есть идея? http://judgecode.com/problems/1011

Учитывая перестановку целых чисел от 0 до n - 1, их сортировка проста. Но что, если вы можете только менять пару целых чисел каждый раз?

Рассчитайте минимальное количество свопов

Answer 1

Один классический алгоритм, кажется, циклов перестановки (https://en.wikipedia.org/wiki/Cycle_notation#Cycle_notation). Количество необходимых свопов равно общему числу элементов, вычитаемых по количеству циклов.

Например:

1 2 3 4 5 
2 5 4 3 1 

Start with 1 and follow the cycle: 
1 down to 2, 2 down to 5, 5 down to 1. 

1 -> 2 -> 5 -> 1 
3 -> 4 -> 3 

Мы должны были бы поменять индекс 1 с 5, а затем индексом 5 с 2; а также индекс 3 с индексом 4. Всего 3 свопа или n - 2. Мы вычитаем n количеством циклов, так как элементы цикла вместе составляют n, и каждый цикл представляет собой своп меньше числа элементов в нем.

Answer 2

Простая реализация в C для вышеуказанной проблемы. Алгоритм похож на пользователя גלעד ברקן:

• магазин положение каждого элемента a[] в b[]. Итак, b[a[i]] = i
• Итерации над начальным массивом a[] слева направо.
• В позиции i, проверьте, соответствует ли a[i] значение i. Если yes, продолжайте повторять.
• Если no, тогда пришло время обменять. Посмотрите на логику кода, чтобы узнать, как происходит обмен. Это самый важный шаг, так как необходимо изменить как массив a[], так и . Увеличение count свопов.

Вот реализация:

long long sortWithSwap(int n, int *a) { 
    int *b = (int*)malloc(sizeof(int)*n); //create a temporary array keeping track of the position of every element 
    int i,tmp,t,valai,posi; 
    for(i=0;i<n;i++){ 
    b[a[i]] = i; 
    } 
    long long ans = 0; 
    for(i=0;i<n;i++){ 
    if(a[i]!=i){ 
     valai = a[i]; 
     posi = b[i]; 
     a[b[i]] = a[i]; 
     a[i] = i; 
     b[i] = i; 
     b[valai] = posi; 
     ans++; 
    } 
    } 
    return ans; 
} 

Answer 3

Суть решения этой проблемы заключается в следующем наблюдении
1. Элементы в массиве не повторять
2. Диапазон элементов от 0 до n-1, где n - размер массива.

Способ подхода
После того, как вы поняли способ приблизиться к проблеме, можно решить ее в линейном времени.

Представьте себе, как выглядит массив после сортировки всех записей?
Это будет выглядеть как arr [i] == i, для всех записей. Это убедительно?

Сначала создайте BOOL массив с именем FIX, где FIX [я] == TRUE, если Ith местоположение фиксировано, инициализировать этот массив с фальшивой первоначально

начать проверку исходного массива для обр матча [я] == i, до тех пор, пока это условие не будет выполнено, все в порядке. При продолжении обхода массива также обновляем FIX [i] = true.
В тот момент, когда вы обнаружите, что arr [i]! = I
вам нужно что-то сделать, arr [i] должно иметь некоторое значение x такое, что x> i, как мы это гарантируем? Гарантия исходит из того, что элементы в массиве не повторяются, поэтому, если массив сортируется до индекса i, это означает, что элемент в позиции i в массиве не может поступать слева, а справа.
Теперь значение x по существу говорит о некотором индексе, почему так, потому что массив имеет только элементы до n-1, начиная с 0, и в отсортированном arry каждый элемент i массива должен находиться в местоположении i.
Что такое arr [i] == x означает, что не только элемент i не находится в правильном положении, но и элемент x отсутствует на своем месте. Теперь, чтобы исправить это местоположение, вам нужно взглянуть на x-е место, потому что, возможно, xth место занимает i, а затем вы меняете элементы по индексам i и x и выполняете задание.
Но подождите, нет необходимости, чтобы индекс x удерживал i (и вы завершаете исправление этих местоположений всего за один обмен). Скорее, возможно, что индекс x содержит значение y, которое снова будет больше i, поскольку массив сортируется только до местоположения i.
Теперь, прежде чем вы сможете исправить положение i, вам нужно исправить x, почему? мы увидим позже.
Итак, теперь вы пытаетесь исправить положение x, а затем аналогичным образом попытаетесь исправить до тех пор, пока вы не увидите элемент i в каком-либо месте в моде.
Мода должна следовать по ссылке от arr [i], пока вы не нажмете элемент i в каком-то индексе.
Гарантируется, что вы обязательно ударите меня в определенном месте, следуя таким образом. Зачем ? попробуйте доказать это, сделайте несколько примеров, и вы почувствуете это.
Теперь вы начнете фиксировать весь индекс, который вы видели по пути, следующему от индекса i до этого индекса (скажем, j). Теперь вы видите, что путь, которым вы следовали, является круглым, и для каждого индекса i, arr [i] обрабатывается в его предыдущем индексе (индекс от того, где вы сюда пришли), и как только вы увидите, что можете исправить индексы и пометить все из них в массиве FIX, чтобы они были истинными. Теперь переходим к следующему индексу массива и делаем то же самое до тех пор, пока не будет исправлен целый массив.
Это была полная идея, но для того, вы свопите, что после того, как вы нашли цикл из n элементов, вам понадобятся n свопов, и после этого вы исправите массив и снова продолжите. Так вот как вы будете считать нет. свопов. Пожалуйста, дайте мне знать, если у вас есть сомнения в подходе. Вы также можете обратиться за помощью к C/C++.
Рад помочь :-)