如何將整數數組分爲偶數和奇數？

-2

我想分區數組（例如[1,2,3,4,5,6,7,8]），第一個分區應該保持偶數值，第二個奇數值（例如結果：[2,4,6,8,1,3,5,7]）。如何將整數數組分爲偶數和奇數？

我設法用內置的Array.prototype方法解決了這個問題兩次。第一種解決方案使用map和sort，僅次於sort。

我想作出第三個解決方案，它使用排序算法，但我不知道什麼算法用於分區列表。我正在考慮冒泡排序，但我認爲它在我的第二個解決方案（array.sort((el1, el2)=>(el1 % 2 - el2 % 2))）中使用...我查看了quicksort，但是我不知道在整數是偶數還是奇數的情況下應用檢查的位置......

什麼是最好的（線性縮放與數組增長）算法來執行這樣的任務就地保持順序的元素？

來源

2017-07-14 Marecky

任何類型最好是'O（nlogn）'，所以如果你想線性縮放，那些不是最好的選擇 – frozen

'sort' ???你有沒有嘗試過使用'filter'？ – Bergi

爲什麼就地？這有什麼目的？ –

如果您正在就地方法，而不是瑣碎的標準return [arr.filter(predicate), arr.filter(notPredicate)]辦法堅持，可以很容易地使用兩個指標，從陣列的兩側運行和交換在必要時有效地實現：

function partitionInplace(arr, predicate) { 
    var i=0, j=arr.length; 
    while (i<j) { 
     while (predicate(arr[i]) && ++i<j); 
     if (i==j) break; 
     while (i<--j && !predicate(arr[j])); 
     if (i==j) break; 
     [arr[i], arr[j]] = [arr[j], arr[i]]; 
     i++; 
    } 
    return i; // the index of the first element not to fulfil the predicate 
}

來源

2017-07-15 01:21:48 Bergi

這與我的回答不一樣嗎？這不會改變分區中項目的相對順序嗎？也就是說，如果給定[1,3,2,4]，結果數組將是[4,2,3,1]？ –

@JimMischel是的，它是一樣的想法，只有我的實現使用任意謂詞，返回陣列分區的位置，因此更復雜的代碼:-)確實交換改變了相對順序，但我很確定沒有算法在'O（n）'時間和'O（1）'空間複雜度中實現穩定的重新排序。 – Bergi

我認爲你是對的，沒有一個穩定的O（n），O（1）解決方案。讓我想起這個笑話（？）：快速，便宜，好：挑選兩個。 –

-1

let evens = arr.filter(i=> i%2==0); 
let odds = arr.filter(i=> i%2==1); 
let result = evens.concat(odds);

我相信那是O（n）。玩的開心。

編輯：或者，如果你真的關心效率：

let evens, odds = [] 
arr.forEach(i=> { 
if(i%2==0) evens.push(i); else odds.push(i); 
}); 
let result = evens.concat(odds);

來源

2017-07-14 23:42:37 frozen

呃，我們可以減少一半的開銷。（這也不是就地，請參閱答案的結尾。） –

編輯@ T.J.Crowder – frozen

仍然不在原地，因爲這個問題明確要求。除了第三個最終陣列之外，還會產生兩個臨時陣列。 *（不是我的dv;我理解它，但不會這麼做）* –

-2

Array.prototype.getEvenOdd= function (arr) { 
    var result = {even:[],odd:[]}; 
    if(arr.length){ 
     for(var i = 0; i < arr.length; i++){ 
     if(arr[i] % 2 = 0) 
      result.odd.push(arr[i]); 
     else 
      result.even.push(arr[i]); 
     } 
    } 
    return result ; 
};

來源

2017-07-14 23:47:19

可以在O（n）的時間做到這一點就地很容易地。在前面開始偶數索引，在後面開始奇數索引。然後，通過數組，跳過第一個偶數的塊。

當您碰到一個奇數時，從末端向後移動以找到第一個偶數。然後交換偶數和奇數。

的代碼看起來是這樣的：

var i; 
var odd = n-1; 
for(i = 0; i < odd; i++) 
{ 
    if(arr[i] % 2 == 1) 
    { 
     // move the odd index backwards until you find the first even number. 
     while (odd > i && arr[odd] % 2 == 1) 
     { 
      odd--; 
     } 
     if (odd > i) 
     { 
      var temp = arr[i]; 
      arr[i] = arr[odd]; 
      arr[odd] = temp; 
     } 
    } 
}

赦免任何語法錯誤。 Javascript並不是我的強項。

請注意，這不會保持相同的相對順序。也就是說，如果你給它的數組[1,2,7,3,6,8]，那麼結果將是[8,2,6,3,7,1]。數組是分區的，但奇數與原始數組的相對順序不同。

來源

2017-07-15 00:18:18

雖然這是有效的，但我認爲部分目標是使其成爲一個穩定的分區，因爲在示例中指定的OP中輸出應保持與每個分區內的輸入相同的順序。 –

@PatrickRoberts：我沒有看到OP特別指出輸出應該穩定。他的例子顯示了一個穩定的安排，但沒有什麼說它必須穩定。不過，這一點並不穩定。我會用這些信息更新我的答案。 –

@PatrickRoberts，謝謝，它應該像你說的那樣保持分區順序。對不起，吉姆我沒有明確地寫。 – Marecky

如何將整數數組分爲偶數和奇數？

回答

相關問題