python - O(logN) 中的排序列表计数元素

Question

假设我有一个排序列表/数组 我需要在 O(logN) 次重复中计算该列表/数组中不同数字的数量 我已经知道我需要使用某种二进制算法，但在最坏的情况下我无法在 O(logN) 次重复中做到这一点 有什么想法吗？

Answer 1

使用bisect模块。

import bisect as b


arr = [1, 1, 1, 2, 2, 3, 3, 3, 3]
for x in [1, 2, 3, 0]:
    print(b.bisect_right(arr, x) - b.bisect_left(arr, x))

输出:

3
2
4
0

因此，该算法适用于您传递给它的任何值。如果传递的值不在列表中，则返回 0。

---

bisect 模块通过使用二分搜索来查找插入给定元素的适当位置。 bisect_left 给出最左边的索引，bisect_right 给出任何现有值右侧的索引。 通过将两者相减，我们得到列表中已存在的 x 值的数量。

由于bisect模块使用二分查找，所以该方法的复杂度为O(log N)。