Gruppierung Numbers JS Algorithmus

Question

ich ein Problem zu lösen versuche:

Problem:

eine Reihe von positiven wiederholenden Zahlen gegeben. Ausgabe sollte ein Array mit einer Quote auf der rechten Seite geben sortiert und nivelliert auf dem links (ohne besondere Reihenfolge)

Input: [4,1,2,3,4]

Output: [4,2 , 3,1]

Löst es in-place und ohne zusätzlichen Raum und O (N) Laufzeit.

Code:

/* 
* 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; 
} 

Ich bin mir nicht sicher, wo ich falsch gehe. Ich vermisse etwas. Ich bekomme das gleiche sortierte Array wie die Ausgabe.

Zustand: ** LÖSEN es INPLACE und ohne zusätzlichen Raum mit ** (vorzugsweise in einer Iteration)

Answer 1

Ich bin mir nicht sicher, wo ich falsch gehe. Ich vermisse etwas. Ich bekomme das gleiche sortierte Array wie die Ausgabe.

mehrere Dinge:

let start = intArr[i]; 
let end = intArr[j]; 
... 
[start, end] = [end, start]; 

diese tauschen sich in der Tat die Werte in den Variablen start und end, aber nicht die Indizes im Array.

Dann haben Sie zwei i++ in der gleichen Schleife, die den linken Zeiger erhöhen.

if(start%2 == 0){ //Even 
    i++; 
} else { 
    [start, end] = [end, start]; //swap 
} 

hier tauschen Sie die Einzelteile, wenn die linke Zeiger zeigt auf einen ungeraden Wert, aber es gibt keine Kontrolle, dass der rechte Zeiger verweist auch auf einen geraden Wert. Sie könnten auch nur zwei ungerade Werte hier tauschen. Gleiches gilt für den rechten Zeiger.

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}

---

wie @JaredSmith vorgeschlagen, das gleiche mit nur einer Art-Funktion :)

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

Eine sehr präzise Methode zur Lösung dieses reduce zu verwenden wäre:

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