排序数组的最小交换次数

本文介绍了排序数组的最小交换次数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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; }

参考