我需要执行以下操作:假设我有一个数组:
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; }
参考
更多推荐
排序数组的最小交换次数
发布评论