arrays - 二进制搜索 - 有人可以清除这个面试算法吗？

Question

我最近接受了一次面试，面试官给了我以下场景，并问我我将使用什么数据结构来实现它:

您有 100 个弹珠，每个弹珠都是红色、蓝色或绿色。弹珠被扔进一个袋子里，你需要有一些机制来取回随机颜色的弹珠(有替换)。

好的，很简单。问了一些关于约束的问题后，我告诉他我会使用一个简单的数组，其中每个桶代表一个弹珠。可以使用随机数函数对数组进行索引，从而生成随机彩色弹珠。

这个解决方案很好，但随后他问“如果你有许多不同的颜色，每种颜色 <= 1,000,000,000 个弹珠怎么办？”最初我建议使用哈希表，其中每个键代表一种颜色，每个值代表该颜色的弹珠数。面试官告诉我这是对空间限制的一个很好的解决，但现在产生 n 种颜色之一的概率是 1/n，而不是大理石总数给出的实际概率。我需要一些方法来保持概率相同而不将它们全部存储在内存中。结果我什么都没想，他给我的解决办法是这样的:

找出每种颜色的总和(这将是 O(n)，这对于设置来说很好)并设置一个数组，其中每个桶代表每种颜色的累积总和。例如，如果您的弹珠总数为 R:3，B:5，G:1,000,000,000，则数组看起来像 [3] [8] [1,000,000,008]。然后他说你现在可以使用带有随机索引的二分搜索来获得随机颜色的大理石，同时仍然保持正确的概率。谁能向我解释为什么会这样？这是否只是一个修改后的二分搜索，返回第一个高于随机索引的值？

Answer 1

诀窍在于您查看二分查找结束的索引而不是该位置的值。我还不知道这个算法。谢谢你的描述。我为你用 python 实现了它:)

import random
import bisect

# 10 red, 20 blue, 70 green
counts = [10, 20, 70]
sums   = [10, 30, 100]

# count how often some color occurs to verify later that the algorithm works correctly
bins = [0, 0, 0]
# randomly select 10000 colors
for _ in range(100000):
    random_index = random.randint(0, sums[-1]) # sums[-1] is the last value in array (100)
    # do binary search in sums array
    result = bisect.bisect_left(sums, random_index)
    bins[result] += 1

print(bins) # example output: [10875, 19732, 69393]