查找分组数字的范围 (log n)

Question

假设一个分组数字数组：

arr = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 8, 8, 8, 8, 8, 4, 4, 4, 4]

我想找到每个数字的范围，假设所有数字都在输入数组中分组在一起。输出应该是：

1: (0,5)
2: (6,10)
3: (11,14)
8: (15,19)
4: (20,23) 

我应用了二分搜索的更改，但我得到的输出是错误的。

我正在寻找具有 log(n) 时间复杂度的解决方案

这是我正在处理的问题的简化版本，构建 ETL 管道，其中访问元素需要下载 100GB 文件。

Answer 1

我正在寻找具有 log(n) 时间复杂度的解决方案

一般情况下这是不可能的；您能做的最好的事情是 O(r + log n) 时间，或（等效地）O(MAX(r, log n)) 时间，其中 r 是范围的数量。 （这是因为您需要构建 r 范围列表才能返回它，并且您无法在少于 θ(r) 时间内完成此操作。）

我使用了二分查找的思想，将区间分成两半，并且仅当中点与其端点不同时才划分子区间。

这大致是正确的方法，但问题在于细节。

我建议做的是r单独的二分搜索——每个范围一个，从左到右——但是使用堆栈来跟踪您之前获取的但比当前范围更靠右的值。您可以使用该堆栈快速查找二分搜索的初始“lo”和“hi”值。这样，您就可以实现渐进最优 O(r + log n) 最坏情况时间。

这是该概念的 JavaScript 实现：

function doIt(arr) {
  const stack = [];
  if (arr.length > 0) {
    stack.push({ pos: arr.length - 1, val: arr[arr.length - 1] });
  }
  stack.push({ pos: 0, val: arr[0] });

  const result = [];

  while (stack.length > 0) {
    const start = stack.pop();

    let lo = start.pos;
    while (stack.length > 0 && stack.at(-1).val === start.val) {
      lo = stack.pop().pos;
    }

    if (stack.length > 0) {
      while (true) {
        const hi = stack.at(-1).pos;

        if (lo + 1 === hi) {
          break;
        }

        const midPos = Math.trunc(lo + (hi - lo) / 2);
        const midVal = arr[midPos];
        if (midVal === start.val) {
          lo = midPos;
        } else {
          stack.push({ pos: midPos, val: midVal });
        }
      }
    }

    result.push({ start: start.pos, end: lo, val: start.val });
  }

  return result;
}

const arr = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 8, 8, 8, 8, 8, 4, 4, 4, 4];

console.log(JSON.stringify(doIt(arr)));