javascript - 将小麦与谷壳分开 - CodeWars 挑战

Question

简介

问题在 Link to challenge for best instructions 上有解释

据我所知，如果左侧的元素大于0。

即[2, -4, 6, -6] => [-6, -4, 6, 2]。

左侧的正极必须与右侧相对的相应“错位”交换。所以，很遗憾我们不能使用

array = array.sort((a, b) => a - b);

最后，左边应该只有负数，右边只有正数。如果数组的长度为奇数，则一个“边”将是一个(或多个)元素，这取决于原始数组中是否有更多的正数或负数。

即[8, 10, -6, -7, 9, 5] => [-7, -6, 10, 8, 9, 5]

方法

为了解决这个问题，我创建了一个相当冗长的算法，将数组分成两半，并跟踪左侧的“错位”(正)元素和右侧的“错位”(负)元素侧，用于交换:

function wheatFromChaff (values) {
  
  //IF ORIGINAL VALUES LENGTH IS EVEN
  if (values.length % 2 === 0) {

    let left = values.slice(0, values.length / 2);
    let right = values.slice(values.length / 2);
    
    let outOfPlaceLeft = left.filter((element) => element > 0);
    let outOfPlaceRight = right.filter((element) => element < 0);

    //replace positive "out of place" left elements with negative "out of place" right elements
    for (let i = 0; i < left.length; i++) {
      if (left[i] > 0) {
        left.splice(i, 1, outOfPlaceRight.pop());
      }
    }
      
    //push remaining "out of place" negative right elements to the left
    while (outOfPlaceRight.length) {
      let first = outOfPlaceRight.shift();
      left.push(first);
    }
    
    //filter out any negatives on the right
    right = right.filter((element) => element > 0).concat(outOfPlaceLeft);

    //concat the remaining positives and return
    return left.concat(right);
  }

  //IF ORIGINAL VALUES LENGTH IS ODD
  if (values.length % 2 !== 0) {

    let left2 = values.slice(0, Math.floor(values.length / 2));
    let right2 = values.slice(Math.ceil(values.length / 2));
    let middle = values[Math.floor(values.length/2)];
    
    let outOfPlaceLeft2 = left2.filter((element) => element > 0);
    let outOfPlaceRight2 = right2.filter((element) => element < 0);

    //replace "out of place", positive left elements
    for (let j = 0; j < left2.length; j++) {
      //if out of there are out of place elements on the right
      if (outOfPlaceRight2.length) {
        if (left2[j] > 0) {
          left2.splice(j, 1, outOfPlaceRight2.pop());
        }
      }
      //if out of place elements on the right are empty
      if (!outOfPlaceRight2.length && middle < 0) {

        if (left2[j] > 0) {
          left2.splice(j, 1, middle);
        }
      }
    }
    
    //filter out negatives on the right
    right2 = right2.filter((element) => element > 0);
    
    //unshift remaining "out of place" positive left elements to the right
    while (outOfPlaceLeft2.length) {
      let first = outOfPlaceLeft2.shift();
      right2.unshift(first);
    }
    if (middle > 0) {
      right2.unshift(middle);
    }
    if (middle < 0) {
      left2.push(middle);
    }
    return left2.concat(right2);
  }
}
console.log(wheatFromChaff([2, -6, -4, 1, -8, -2]));

有时以前的方法行得通，但它在 Codewars 上给我一个错误:

AssertionError [ERR_ASSERTION]: [ -10, 7 ] deepEqual [ -10, -3, 7 ]

你认为我的逻辑有什么缺陷吗？对更好的策略有什么建议吗？

Answer 1

我已经使用两个 “指针” 解决了这个问题，一个从数组的 head 开始，另一个从 tail 开始阵列。这个想法是，在每次迭代中，递增 head 或递减 tail 迭代，直到您在 head 指针上找到一个正数并且tail 指针处的负数。当满足此条件时，您必须对元素的位置进行交换并继续。最后，当 head 指针大于 tail 指针时，您必须停止循环。

function wheatFromChaff(values)
{
    let res = [];
    let head = 0, tail = values.length - 1;

    while (head <= tail)
    {
       if (values[head] < 0)
       {
           res[head] = values[head++];
       }
       else if (values[tail] > 0)
       {
           res[tail] = values[tail--];
       }
       else
       {
           res[tail] = values[head];
           res[head++] = values[tail--];
       }
    }

    return res;
}

console.log(wheatFromChaff([2, -4, 6, -6]));
console.log(wheatFromChaff([8, 10, -6, -7, 9]));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

此方法通过了该链接中提到的所有测试:

Time: 894ms Passed: 5 Failed: 0

但也许有更好的解决方案。