如何找到在javascript中按降序排序数字数组所需的最小交换次数 [英] How to find the Minimum number of swaps required for sorting an array of numbers in descending order in javascript

问题描述

我正在尝试让我的代码执行此操作：

原始数组= [1,2,3,4]交换一次 - > [4,2 ，3,1]再次交换 - > [4,3,2,1]

因此结果是2

<但是它不起作用。这是我到目前为止所拥有的：

  function check（arr）{var sarr = []; var cnt = 0; var arrL = arr.length; //创建数组的第二个副本以供参考var arrCopy = [... arr]; for（let i = 0; i< arrL; i ++）{var maxV = Math.max（... arr）; sarr.push（MAXV）; let pos = arr.indexOf（maxV）; //删除找到的号码arr.splice（pos，1）; //检查新数组中的数字索引是否与副本相同，如果没有，那么有一个交换让ai = arrCopy.indexOf（maxV）;设si = sarr.indexOf（maxV）; if（ai！== si&&（i + 1）！= arrL&& pos！== 0）{cnt ++; }; } console.log（cnt）;} check（[1,2,3,4,5,6]）; //结果应为3check（[6,5,4,3,2,1]）; //结果应为0check（[1,2,3,4]）; //结果应为2check（[1,3,2,5,4,6]）; //结果应该是3check（[1,2,10,4,5,6,7,8,9,3,12,11]）; //结果应该是6check（[49,37,9,19， 27,3,25,11,53,42,57,50,55,56,38,48,6,33,28,8,20,31,51,14,23,4,5,5,52,36， 22,41,47,39,2,7,13,45,1,42,32,10,15,21,30,17,60,29,5,59,12,40,24,54,46， 26,43,35,34,18,16]）; //结果应为54  

有人可以让我知道我做错了吗？

解决方案

我会先说一个数组的副本按降序排列，以获得项目的正确索引。

出于实际原因，（或者只是包含检查和减少的循环的较短概念） ，我从数组的末尾循环。

然后我检查数组和<$ c $的值c>在dame索引处反转并继续迭代。

如果不是相同的值，则需要位置的项目 i 和实际位置交换 p 并且计数递增。

最后返回计数。

  function check（array）{var reversed = array.slice（）。sort（（a，b） ）=> b  -  a），count = 0，i = array.length，p; while（i--）{if（array [i] === reversed [i]）继续; p = array.indexOf（reverse [i]）; [array [i]，array [p]] = [array [p]，array [i]];计数++; } console.log（... array）; return count;} console.log（check（[1,2,3,4,5,6]））; // 3console.log（check（[6,5,4,3,2,1]））; // 0console.log（check（[1,2,3,4]））; // 2console.log（check（[1,3,2,5,4,6]））; // 3console.log（检查（[1,2,10,4,5,6,7,8,9,3,12,11]））; // 6console.log（检查（[49,37,9,19,27,3,25,11,53,42,57,50,55,56,38,48,6,33,28,8,20] ，31,51,14,23,4,58,52,36,22,41,47,39,2,7,13,45,1,42,32,10,15,21,30,17,60 ，29,5,59,12,40,24,54,46,26,43,35,34,18,16]））; // 54  

  .as-console-wrapper {max-身高：100％！重要;顶部：0; }  

I'm trying to get my code to do this:

Original array = [1,2,3,4] swap once-> [4,2,3,1] swap again->[4,3,2,1]

Therefore result is 2

But it's not working. Here's what I have so far:

   

 function check(arr){
	var sarr = [];
	var cnt = 0;
	var arrL = arr.length;
   // Create a second copy of the array for reference
	var arrCopy = [...arr];
	for(let i=0; i<arrL;i++){
		var maxV = Math.max(...arr);
		sarr.push(maxV);
		let pos = arr.indexOf(maxV);
		// Remove the found number
		arr.splice(pos,1);
		// Check if the index of the number in the new array is same with the copy, if not then there was a swap
		let ai =arrCopy.indexOf(maxV); 
		let si =sarr.indexOf(maxV);
		if (ai !== si && (i+1)!=arrL && pos !== 0){
		cnt++;
        };
	}

	console.log(cnt);
}

check([1, 2, 3, 4, 5, 6]);//Result should be 3
check([6,5,4,3,2,1]); //result should be 0

check([1,2,3,4]); //result should be 2

check([1,3,2,5,4,6]); //result should be 3

check([1,2,10,4,5,6,7,8,9,3,12,11]);//result should be 6

check([ 49, 37, 9, 19, 27, 3, 25, 11, 53,  42, 57, 50, 55,  56, 38, 48, 6, 33, 28, 8, 20, 31, 51, 14, 23, 4, 58, 52, 36, 22, 41, 47, 39, 2, 7, 13, 45, 1, 44, 32, 10, 15, 21, 30, 17,  60, 29, 5, 59, 12, 40, 24, 54, 46, 26, 43, 35, 34, 18, 16]);//result should be 54

Can someone please let me know what I'm doing wrong?

解决方案

I would start with a copy of the array in descending order for getting the right index of the items.

For practical reasons, (or just a shorter conceprion of the loop with including check and decrement), i loop from the end of the array.

Then I check the value of array and reversed at the dame index and go on with the iteration.

If not the same value, the items at the wanted position i and the actual position p are swapped and the count incremented.

At the end the count is returned.

function check(array) {
  var reversed = array.slice().sort((a, b) => b - a),
      count = 0,
      i = array.length,
      p;

  while (i--) {
      if (array[i] === reversed[i]) continue;
      p = array.indexOf(reversed[i]);
      [array[i], array[p]] = [array[p], array[i]];
      count++;
  }
  console.log(...array);
  return count;
}

console.log(check([1, 2, 3, 4, 5, 6])); // 3
console.log(check([6, 5, 4, 3, 2, 1])); // 0
console.log(check([1, 2, 3, 4])); // 2
console.log(check([1, 3, 2, 5, 4, 6])); // 3
console.log(check([1, 2, 10, 4, 5, 6, 7, 8, 9, 3, 12, 11])); // 6
console.log(check([ 49, 37, 9, 19, 27, 3, 25, 11, 53,  42, 57, 50, 55,  56, 38, 48, 6, 33, 28, 8, 20, 31, 51, 14, 23, 4, 58, 52, 36, 22, 41, 47, 39, 2, 7, 13, 45, 1, 44, 32, 10, 15, 21, 30, 17,  60, 29, 5, 59, 12, 40, 24, 54, 46, 26, 43, 35, 34, 18, 16])); // 54

.as-console-wrapper { max-height: 100% !important; top: 0; }

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