将小麦从糠- CodeWars挑战中分离出来

Question

引言

这个问题在链接到“挑战最佳指示”上解释了。

据我所知，如果左侧的元素大于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]));

​

有时，前面的方法可以工作，但它在Codewar上给出了一个错误：

AssertionError ERR_ASSERTION：-10，7 deepEqual -10，-3，7

你看到我的逻辑有什么缺陷吗？有更好的策略建议吗？

Answer 1

我使用两个"pointers"来解决这个问题，一个从数组的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;}

​

该方法通过了该链接上提到的所有测试：

时间:894通过:5失败:0

但也许有更好的解决办法。

Answer 2

另一种方法是使用indexOf()和lastIndexOf()助手函数：

​

function lastIndexOf(arr, pred, start) {
  start = start || arr.length - 1;
  for (let i = start; i >= 0; i--) {
    if (pred(arr[i])) return i;
  }
  return -1;
}

function indexOf(arr, pred, start = 0) {
  for (let length = arr.length, i = start; i < length; i++) {
    if (pred(arr[i])) return i;
  }
  return Infinity;
}

function wheatFromChaff(values) {
    
    let firstPos = indexOf(values, x => x > 0);
    let lastNeg = lastIndexOf(values, x => x < 0);
    
    while ( firstPos < lastNeg ) {
      let a = values[firstPos];
      let b = values[lastNeg];
      values[firstPos] = b;
      values[lastNeg] = a;
      
      firstPos = indexOf(values, x => x > 0, firstPos);
      lastNeg = lastIndexOf(values, x => x < 0, lastNeg);
    }
    return values;
}
console.log(wheatFromChaff([2, -6, -4, 1, -8, -2]));

​