将小麦与谷壳分开 - 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

我已经使用两个 "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;}

此方法通过了 link 中提到的所有测试：

Time: 894ms Passed: 5 Failed: 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]));

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

Separate The Wheat From The Chaff - CodeWars Challenge

javascript

arrays

splice

简介

方法