分组编号JS算法
分组编号JS算法
提问于 2017-08-12 22:50:51
我想解决一个问题：
问题：
给出一组正数的重复数字。输出应该给出一个数组，数组在右边排序，在左边均数(没有特定的顺序)。 投入: 4,1,2,3,4 产出: 4,2,3,1 在不使用额外空间和O(N)运行时的情况下，就地解决它.
代码：
/*
* Algorithm is simple, have two pointers one on the left and another on the right.
* Note: We are sorting all evens on the left and odds on the right
* If you see even on left, move on else swap.
*/
function groupNumbers(intArr) {
if(intArr.length == 0 || intArr.length == 1){
return intArr;
}
for(let i=0, j =intArr.length-1; i<intArr.length; i++){
if(j>=i){ //elements should not overlap
let start = intArr[i];
let end = intArr[j];
if(start%2 == 0){ //Even
i++;
} else {
[start, end] = [end, start]; //swap
}
if(end%2 == 1){
j--;
} else {
[start, end] = [end, start]; //swap
}
} //if-ends
}//for-ends
return intArr;
}我不知道我哪里出了问题。我漏掉了什么。我得到了与输出相同的排序数组。
条件： **在不使用额外空间的情况下就地解决**(最好在一次迭代中)
回答 2
Stack Overflow用户
回答已采纳
发布于 2017-08-13 00:21:42
我不知道我哪里出了问题。我漏掉了什么。我得到了与输出相同的排序数组。
有几件事：
let start = intArr[i];
let end = intArr[j];
...
[start, end] = [end, start];这确实会交换变量start和end中的值，而不是数组中的索引。
然后，在相同的循环中有两个i++来增加左指针。
if(start%2 == 0){ //Even
i++;
} else {
[start, end] = [end, start]; //swap
}在这里，当左指针指向奇数值时，您可以交换项，但是没有检查右指针是否也指向偶数值。你最好在这里交换两个奇数。右指针也一样。
const isEven = v => (v&1) === 0;
const isOdd = v => (v&1) === 1;
function groupNumbers(arr){
var left = 0, right = arr.length-1;
while(left < right){
//move the left pointer to find the next odd value on the left
while(left < right && isEven(arr[left])) ++left;
//move the right pointer to find the next even value on the right
while(left < right && isOdd(arr[right])) --right;
//checking that the two pointer didn't pass each other
if(left < right) {
console.log("swapping %i and %i", arr[left], arr[right]);
//at this point I know for sure that I have an odd value at the left pointer
//and an even value at the right pointer
//swap the items
var tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
}
return arr;
}
[
[1,2,3,4],
[1,2,3,4,5,6,7,8,9,0],
[1,3,5,7],
[2,4,1,3],
[5,4,3,2,1],
].forEach(sequence => {
console.log("\ninput: " + sequence);
console.log("output: " + groupNumbers(sequence));
});.as-console-wrapper{top:0;max-height:100%!important}
正如@JaredSmith所建议的那样，使用排序函数也是一样的:)
function sortEvenLeftOddRight(a,b){
return (a&1) - (b&1);
//return (a&1) - (b&1) || a-b; //to additionally sort by value
}
[
[1,2,3,4],
[1,2,3,4,5,6,7,8,9,0],
[1,3,5,7],
[2,4,1,3],
[5,4,3,2,1],
].forEach(sequence => {
console.log("\ninput: " + sequence);
sequence.sort(sortEvenLeftOddRight);
console.log("output: " + sequence);
});.as-console-wrapper{top:0;max-height:100%!important}
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/45655584
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号