js 数组中某个值连续出现的次数

Question

var aa = [
    { 'id': 0, 'age': 16 },
    { 'id': 1, 'age': 16 },
    { 'id': 2, 'age': 12 },
    { 'id': 3, 'age': 16 },
    { 'id': 4, 'age': 16 },
    { 'id': 5, 'age': 16 }
]

怎么查找出 连续age=16 的次数
结果是3

Answer 1

2022-03-20 更新

@miganzi 的思路非常好，不过代码略微复杂了一点。这个算法的核心就是：既然我已经找到了最大 count，那下次直接跳过最大 count 数，如果正好命中，那就向前向后双向统计汇总出来看是否最大，否则继续跳过最大连续数……

按这个思路写的代码（看注释）

function countContinuous(list, predicate) {
    let maxCount = 0;

    const handledIndex = 0;
    const end = list.length;

    // 因为就是索引的移动，可以用 for 循环，这和 while (i < end) 差不多
    // 每次处理之后跳过 maxCount，并向下多移一位（也就是要大于 maxCount 的情况才需要重算 maxCount）
    for (let i = handledIndex; i < end; i += maxCount + 1) {
        if (predicate(list[i])) {
            // 如果命中，分别向前向后查找，并合并计数
            const forwardCount = findForward(i);
            maxCount = Math.max(maxCount, forwardCount + findBackward(i));
        }
    }
    return maxCount;

    // 在当前位置向前、后两个方面查找，也可 以直接写在上面的循环中，
    // 但是为了让逻辑看起来更清晰，抽取了两个局部函数

    // 正向（继续）查找，计数含当前位置索引
    function findForward(current) {
        let count = 0;
        for (let i = current + 1; i < end; i++, count++) {
            if (!predicate(list[i])) { break; }
        }
        return count + 1;
    }

    // 反向查找，不含当前位置
    function findBackward(current) {
        let count = 0;
        for (let i = current - 1; i > handledIndex; i--, count++) {
            if (!predicate(list[i])) { break; }
        }
        return count;
    }
}

也做了性能对比，在这里 JSBench.me 上的性能对比。

---

之前的答案

function countContinuous(list, predicate) {
    let count = 0;      // 用于当前连续计数
    let maxCount = 0;   // 保存最大连续计数
    list.forEach(it => {
        if (predicate(it)) {
            count++;
        } else {
            // 当次连续结束，跟 maxCount 比较保留较大的一个
            maxCount = Math.max(maxCount, count);
            count = 0;
        }
    });

    // 最后一次当前连续计数并没有跟 maxCount 进行比较，所以要补一次
    return Math.max(maxCount, count);
}

console.log(countContinuous(aa, it => it.age === 16));

Answer 2

如果数据量较少的话，使用循环的方式就可以了。如果数据量较大，则可以利用已经查找到的最大匹配值信息值来做查找上的优化。

const findRepeatForward = (
  startIndex,
  curForward = 1,
  options = {},
  forward = curForward
) => {
  const { maxIndex } = options;
  let lastIndex = startIndex + curForward;
  if (lastIndex > maxIndex) {
    // 如果最后的值已经超出数组最大范围
    // 则表示后续值不需要再判断
    return {
      forward,
      index: maxIndex + 1,
    };
  } else {
    // 从后往前查找索引
    const { findHandle } = options;
    let prevIndex = lastIndex;
    while (prevIndex > startIndex) {
      if (findHandle(values[prevIndex])) {
        prevIndex--;
      } else {
        break;
      }
    }
    if (prevIndex === startIndex) {
      // 全部匹配，继续往后查找，进一步更新forward值
      let index = lastIndex + 1;
      for (; index <= maxIndex; index++) {
        if (findHandle(values[index])) {
          forward++;
        } else {
          break;
        }
      }
      return {
        found: true,
        forward: forward + 1,
        index: index + 1,
      };
    } else if (prevIndex === lastIndex) {
      // 一个匹配都没有
      return {
        forward,
        index: lastIndex + 1,
      };
    } else {
      // 找到部分匹配，递归找到完全匹配或完全不匹配为止
      let equalCount = lastIndex - prevIndex;
      return findRepeatForward(
        lastIndex,
        forward - equalCount + 1,
        options,
        forward
      );
    }
  }
};
const getContinousCount = (values, findHandle) => {
  const maxIndex = values.length - 1;
  let i = 0;
  let forward;
  while (i <= maxIndex) {
    const curItem = values[i];
    if (findHandle(curItem)) {
      const result = findRepeatForward(i, forward, {
        maxIndex,
        values,
        findHandle,
      });
      i = result.index;
      forward = result.forward;
    } else {
      i++;
    }
  }
  return forward ?? 0;
};
console.log(getContinousCount(aa, it => it.age === 16));

小数据量的情况下性能上没有太大的差别，当数据量较大的时候，最大重复值越大，找到的时间越早，使用以上方式查找性能就越好。相比常规方式大概有3倍以上的性能提升（如果不是数据量特别大或者执行次数特别多，这点性能提升可能也没有多大意义），仅为了探索，用了上面两位大大的方案对比做了个简单的性能测试：jsbin性能测试 感兴趣的同学可以看一看~

Answer 3

遍历就行，遇到不是16的记录然后归零，然后返回记录最大值。

const aa = [{'id':0, 'age': 16},{'id':1, 'age': 16},{'id':2, 'age': 12},{'id':3, 'age': 16},{'id':4, 'age': 16},{'id':5, 'age': 16}]
let res=0
let now=0
for (const i of aa) {
    if (i.age==16){
        now++
    }else{
        if (res<now){
            res=now
        }
        now=0
    }
}
if (res<now){
    res=now
}
console.log(res);

Answer 4

function count(arr, key, value) {
    var ret = 0;
    for (var i = 0, j = 0; i < arr.length; ++i) {
        if (arr[i][key] !== value) j = 0;
        else if (ret < ++j) ret = j;
    }
    return ret;
}
console.dir(count(aa, "age", 16));