排序数组的最小交换次数 [英] 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屋!