排序数组的最小交换次数 [英] Minimum number of swaps to sort an array

问题描述

我需要执行以下操作：假设我有一个数组：

I need to do something like this: Let's say I have an array:

 [3, 4, 1, 2]

我需要交换3和4，以及1和2，所以我的数组看起来像 [4，3，2，1] 。现在，我可以执行 sort（）。在这里，我需要计算将初始数组更改为最终输出所需的迭代次数。示例：

I need to swap 3 and 4, and 1 and 2, so my array looks like [4, 3, 2, 1]. Now, I can just do the sort(). Here I need to count how many iterations I need, to change the initial array to the final output. Example:

// I can sort one pair per iteration
let array = [3, 4, 1, 2, 5]
let counter = 0;

//swap 3 and 4
counter++;
// swap 1 and 2
counter++;
// 5 goes to first place
counter++

// now counter = 3 <-- what I need

编辑：这是我尝试的。并非总是如此，这是因为以下问题：气泡排序算法JavaScript

Here is what I tried. doesn't work always tho... it is from this question: Bubble sort algorithm JavaScript

let counter = 0;
    let swapped;
    do {
        swapped = false;
        for (var i = 0; i < array.length - 1; i++) {
            if (array[i] < array[i + 1]) {
                const temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = true;
                counter++;
            }
        }
    } while (swapped);

编辑：并非总是正确的，因为我可以交换位置例如从最后到第一。看看上面的示例代码，现在就对其进行编辑。

EDIT: It is not correct all the time because I can swap places from last to first, for example. Look at the example code above, it is edited now.

推荐答案

这是我最理想的代码到目前为止已经尝试过，答案％5D = interview-preparation-kit& playlist_slugs％5B％5D = arrays rel = nofollow noreferrer>黑客等级：

function minimumSwaps(arr) {
    var arrLength = arr.length;

    // create two new Arrays 
    // one record value and key separately
    // second to keep visited node count (default set false to all)

    var newArr = [];
    var newArrVisited = [];
    for (let i = 0; i < arrLength; i++) {
        newArr[i]= [];
        newArr[i].value = arr[i];
        newArr[i].key = i;
        newArrVisited[i] = false;
    }

    // sort new array by value

    newArr.sort(function (a, b) {
        return a.value - b.value;
    })

    var swp = 0;
    for (let i = 0; i < arrLength; i++) {

        // check if already visited or swapped
        if (newArr[i].key == i || newArrVisited[i]) {
            continue;
        }

        var cycle = 0;
        var j = i;
        while (!newArrVisited[j]) {

            // mark as visited
            newArrVisited[j] = true;
            j = newArr[j].key; //assign next key
            cycle++;
        }
        if (cycle > 0) {
            swp += (cycle > 1) ? cycle - 1 : cycle;
        } 

    }
    return swp;
}

参考

这篇关于排序数组的最小交换次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！