如何将整数数组分为偶数和奇数？

-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

如何将整数数组分为偶数和奇数？

回答

相关问题