有序数组按无重叠区间桶统计元素数量：求更优实现方案

我们需要实现一个函数：接收升序排列的数字数组array，以及无重叠、相邻区间仅差1的有序桶数组buckets，统计每个桶内包含的array元素数量。比如示例中summarize([0, 10, 60, 120], [[0, 59], [60, 90]])需返回[2, 1]。原代码可运行但逻辑分支冗余、边界处理不够严谨，以下是两种更简洁健壮的实现方案：

方法一：双指针法（高效简洁，适合常规场景） #

利用array和buckets均为有序的特性，用双指针一次遍历完成统计，时间复杂度O(n)（n为数组长度）：

function summarize(array, buckets) {
  const result = new Array(buckets.length).fill(0);
  let arrIdx = 0;
  const arrLen = array.length;

  for (let bucketIdx = 0; bucketIdx < buckets.length; bucketIdx++) {
    const [start, end] = buckets[bucketIdx];
    // 跳过数组中小于当前桶起始的元素（数组升序，无需回头）
    while (arrIdx < arrLen && array[arrIdx] < start) {
      arrIdx++;
    }
    // 统计当前桶内的元素
    while (arrIdx < arrLen && array[arrIdx] <= end) {
      result[bucketIdx]++;
      arrIdx++;
    }
    // 数组遍历完成后提前退出，避免无效循环
    if (arrIdx >= arrLen) break;
  }
  return result;
}

核心思路： #

• 双指针分别跟踪数组遍历位置arrIdx和当前处理的桶bucketIdx
• 先跳过所有小于当前桶起始的元素，再连续统计落在桶区间内的元素
• 数组遍历完成后直接终止循环，减少不必要的计算
• 天然处理所有边界情况：元素小于所有桶、大于所有桶、刚好落在区间端点等

方法二：二分查找法（适合大数据量场景） #

如果array数据量极大，二分查找可以快速定位每个桶对应的元素范围，时间复杂度O(m log n)（m为桶的数量，n为数组长度）：

function summarize(array, buckets) {
  // 封装二分查找：找到第一个满足条件的元素索引
  const findFirstIndex = (condition) => {
    let left = 0;
    let right = array.length;
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (condition(array[mid])) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  };

  return buckets.map(([start, end]) => {
    // 找到第一个 >= start 的元素索引
    const startIdx = findFirstIndex(num => num >= start);
    // 找到第一个 > end 的元素索引
    const endIdx = findFirstIndex(num => num > end);
    // 差值即为当前桶内的元素数量
    return endIdx - startIdx;
  });
}

核心思路： #

• 对每个桶，用两次二分查找分别定位区间的左右边界在数组中的位置
• 两个索引的差值就是当前桶包含的元素数量
• 无需遍历整个数组，适合数组极大但桶数量较少的场景

对比原代码的优势 #

• 逻辑更清晰，分支更少，可读性更强
• 边界处理全面覆盖所有极端情况
• 性能更稳定，避免原代码中指针移动的冗余判断

内容的提问来源于stack exchange，提问作者Joji