我最近参加了一次面试，面试官给了我以下场景，问我将使用什么数据结构来实现它:
你有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]。然后他说，你现在可以使用带有随机索引的二分搜索来获得一个随机颜色的弹珠，同时仍然保持正确的概率。有人能给我解释一下为什么会这样吗?这只是一个修改后的二进制搜索，返回第一个比随机索引高的值吗?
诀窍是查看二进制搜索结束的索引，而不是该位置的值。我还不知道这个算法。谢谢你的描述。我用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]
如果选择大理石颜色的随机索引在1到N之间，那么获得特定颜色的概率是k/N，其中k是分配给该颜色的数字数。你的采访者只是简单地将颜色按顺序排列，以便每种颜色都有正确的k个分配索引(其中k是该颜色的原始弹珠的数量)，然后注意到给定1到N之间的随机索引，您可以进行二分搜索以找到该随机索引所在的颜色范围。假设1到N之间的随机索引是均匀随机的，那么当有k个弹珠具有该颜色时，得到该颜色的正确概率为k/N。