题目重点：当 N 很大、不同值 K 很小时，按段首二分下一个值；区别随机访问复杂度与实际 IO。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 数组可随机访问且升序（允许重复）；返回不同值个数，空数组为 0。题目未说明数据是在内存、mmap、远程块存储还是只能流式读取。
- 训练代码假设比较和下标访问为 O(1)；若远程读，必须重新估算 IO/延迟。
解题路线
- 从 i=0 开始取当前值 v，二分搜索 [i+1,N) 中第一个 >v 的位置 j，也就是当前连续重复段的右边界；计数+1 并令 i=j。
- 边界不存在时 j=N，结束。每轮至少跳过一个完整 distinct 段，恰好 K 轮。单轮二分搜索至多 log N 次比较，总 O(K log N)。
- 可用指数搜索先找段边界上界再二分，时间 O(Σ log run_length)；当段长差异很大时减少早期无谓比较。
- 若数组只能顺序扫描，则随机二分不可行，必须 O(N) 读或先建块索引；若存储按块且重复跨块，记录块首尾及 distinct 摘要可减少 IO。题目的分治递归在全异值时必须看完所有叶子，最坏 O(N)。
手动走一遍
[1,1,1,4,4,9,9,9,9]：i=0 取 1，二分跳到 3；取 4 跳到 5；取 9 跳到 9，答案 3。全相同只跑一次二分；全不同有 K=N，可能比线性扫描更慢，应检测或直接扫描。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def count_distinct_sorted(array) -> int:
"""Random-access sorted sequence; counts distinct values without scanning runs."""
n = len(array)
count = 0
i = 0
while i < n:
value = array[i]
lo, hi = i + 1, n
while lo < hi:
mid = (lo + hi) // 2
if array[mid] <= value:
lo = mid + 1
else:
hi = mid
i = lo
count += 1
return count
复杂度
随机访问模型下 O(K log N) 时间、O(1) 额外空间；朴素扫描 O(N)。指数搜索可写成 O(Σ log rᵢ)，rᵢ 各段长度。训练代码与 20,000 组随机有序数组的 set 大小对照通过。
易错点与追问
容易失分的边界
- 二分找最后一个等值位置后没有 +1，陷入死循环。
- 把随机访问 O(1) 假设直接套到远程十亿元素文件。
- 说分治写法始终 O(K log N)，忽略全不同退化。
- K 接近 N 仍坚持每个元素再做二分。
- 未处理空数组。
继续深挖
- 只能顺序访问时还能比 O(N) 快吗？
- 分块存储如何设计块级目录？
- 数组持续追加且保持排序时如何增量维护 distinct？
- 若数组非降序但允许数据质量错误，如何验证？
