分組號JS算法

Question

我試圖解決一個問題：

問題：

給定的正重複號的數組。輸出 應該得到具有排序右側賠率的陣列和脣上上 左側（沒有特定的順序）

輸入：[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; 
} 

我不知道我要去哪裏錯了。我錯過了一些東西。我得到與輸出相同的排序數組。

條件： **解決它INPLACE和不使用額外的空間**（優選在一個迭代）

Answer 1

我不確定我要去哪裏錯。我錯過了一些東西。我得到與輸出相同的排序數組。

幾件事情：

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}

Answer 2

一個非常簡潔的方法來解決，這將是使用reduce：

const out = arr.reduce((p, c) => { 

    // if the value is divisible by 2 add it 
    // to the start of the array, otherwise push it to the end 
    c % 2 === 0 ? p.unshift(c) : p.push(c) 
    return p; 
}, []); 

OUT

[4,2,4,1,3] 

DEMO