如何在不使用其他数组的情况下过滤数组

Question

到目前为止，我已经尝试过了，但是它返回了未过滤的数组：

function filterRangeInPlace(array, min, max) {
  array = array.filter(item => (item >= min && item <= max));
  console.log(array);
}

let arr = [5, 3, 8, 1];

filterRangeInPlace(arr, 1, 4);

console.log(arr);

Answer 1

如果在不创建另一个数组的情况下就地进行过滤实际上很重要，那么您必须像老派一样使用两个索引遍历数组，并在此过程中复制值。每次遇到未通过过滤器测试的元素时，都会增加一个索引而不是另一个索引。最后，您将数组重置.length为尾随索引：

function filterInPlace(array, fn) {
  let from = 0, to = 0;
  while (from < array.length) {
    if (fn(array[from])) {
      array[to] = array[from];
      to++;
    }
    from++;
  }
  array.length = to;
}

这具有 O(n) 的优点，只需通过数组一次，而涉及的解决方案.splice()为 O(n ² )。

要进行“范围检查”，您可以编写另一个函数来创建给定最小值和最大值的过滤谓词：

function rangePredicate(min, max) {
  return n => n >= min && n <= max;
}

然后你可以将它的返回值传递给过滤器函数：

var arr = [1, 2, 3, ... ];
filterInPlace(arr, rangePredicate(0, 10));