按值将相邻的数组项分组的最佳方式

Question

假设我们有一个数值数组：

[5, 5, 3, 5, 3, 3]

什么是按值和相邻性分组的最佳方法。结果应如下所示：

[ [5,5], [3], [5], [3,3] ]

当然，我可以循环遍历源数组并查找下一个/上一个项目，如果它们相同，则将它们推送到临时数组，然后将其推送到结果数组中。

但我喜欢用函数式的方式编写代码。所以也许有更好的方法？

- Girafa

Answer 1

您可以使用 Array.prototype.reduce 方法：

var result = [5, 5, 3, 5, 3, 3].reduce(function(prev, curr) {
    if (prev.length && curr === prev[prev.length - 1][0]) {
        prev[prev.length - 1].push(curr);
    }
    else {
        prev.push([curr]);
    }
    return prev;
}, []);

alert( JSON.stringify(result) );

- dfsq

---

关于这段代码的一些注释：prev是到目前为止已经构建的数组部分，curr是我们正在查看的元素。我们要么将其添加到分组数组中的最后一个数组中，要么开始一个新的数组。如果prev.length为0，则其值为false，这可以防止我们在第一次迭代中访问索引-1。 - Gamma032

Answer 2

如果您想谈论性能，n-复杂度[O(n)]是您将获得的（您所谈论的唯一迭代）。如果您想谈论内存使用优化，也许您会希望推入/弹出对象（而不是复制它们）。或者在创建输入数组时将其组织为数组的数组（例如，[ [5]，[5]，[3]，[5]，[3]，[3]]），并仅在此数组上工作，以将其形状塑造成您所追求的最终形式。如果您想在实现中更加花哨，可以尝试实现递归函数来处理它（但通常情况下，在提供相同性能的两种实现之间，您应该选择更容易阅读的那个）。

- Lucian

Answer 3

这是一个很好的使用场景，可以使用不常见的Array.prototype.reduceRight函数 -

const data =
  [ 5, 5, 3, 5, 3, 3 ]
  
const groupAdjacent = (a = []) =>
  a.reduceRight
    ( ([ group = [], ...result ], v) =>
        group.length
          ? group[0] === v
              ? [ [ v, ...group ], ...result ] // v matches group
              : [ [ v ], group, ...result ]    // v does not match group
          : [ [ v ], ...result ]               // no group to compare
    , [[]]
    )
        
console.log(groupAdjacent(data))
// [ [ 5, 5 ], [ 3 ], [ 5 ], [ 3, 3 ] ]

console.log(groupAdjacent([]))
// [ [] ]

同样的过程可以使用传递续体方式来描述 -

const data =
  [ 5, 5, 3, 5, 3, 3 ]
  
const identity = x =>
  x
  
const None =
  Symbol ()
  
const groupAdjacent = ([ v = None, ...more ], k = identity) =>
  v === None
    ? k ([[]])
    : groupAdjacent (more, ([ group, ...result ]) =>
        group.length
          ? group[0] === v
              ? k ([ [ v, ...group ], ...result ]) // v matches group
              : k ([ [ v ], group, ...result ])    // v does not match group
          : k ([ [ v ], ...result ])               // no group to compare
      )
        
console.log(groupAdjacent(data))
// [ [ 5, 5 ], [ 3 ], [ 5 ], [ 3, 3 ] ]

console.log(groupAdjacent([]))
// [ [] ]

- Mulan

Answer 4

我有一个相同的需求，但是需要按每个值的函数分组（而不是值本身）。例如，

[1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 42]

成为

[[1, 3, 5], [2, 4, 6], [7], [8], [9], [10, 42]]

给定分组函数。

function (a) { return a % 2; }

一种方法是扩展 @dfsq 的方法，但使用按字典顺序作用域的 fn_prev 来避免重新计算先前的 fn（val）。

var fn_prev = null;
myArray.reduce((acc, val) => {
  let fn_curr = fn(val);
  if (!acc.length || fn_curr !== fn_prev) {
    acc.push([val]);
  } else {
    acc[acc.length - 1].push(val);
  }
  fn_prev = fn_curr;
  return acc;
}, []);

我觉得避免使用.reduce更为直接:

let fn_prev = null;
let acc = [];
for (let val of myArray) {
  let fn_curr = fn(val);
  if (!acc.length || fn_curr !== fn_prev) {
    acc.push([val]);
  } else {
    acc[acc.length - 1].push(val);
  }
  fn_prev = fn_curr;
}
console.log(acc);

这可以像以下这样添加到数组原型中：

Object.defineProperty(Array.prototype, 'groupByAdjacent', {
  value: function(fn) {
    let fn_prev = null;
    let acc = [];
    for (let val of [].concat(this)) {
      let fn_curr = fn(val);
      if (!acc.length || fn_curr !== fn_prev) {
        acc.push([val]);
      } else {
        acc[acc.length - 1].push(val);
      }
      fn_prev = fn_curr;
    }
    return acc;
  }
});

并且像这样使用：

let x = [1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 42];
let grouped_x = x.groupByAdjacent(a => a % 2);
console.log(grouped_x);

- Andrew Cheong