arrays - 如何使用元素值除以数组总和的概率返回元素的索引

Question

给定一个数组和一个值 k，编写一个函数以 k/sum(输入数组)的概率返回等于 k ​​的元素的索引。假设输入数组中没有重复的数字。

例如，如果输入数组是 1,4,2,3。该函数应具有以下行为:

以 1/10 的概率返回 0；

以 4/10 的概率返回 1；

以 2/10 的概率返回 2；

以 3/10 的概率返回 3；

问题2:数组中出现重复项如何处理？

我一直认为二分搜索可以很好地找到数组中的元素，但我还没有想出如何将它与概率联系起来。

已编辑:根据建议，this question类似于我的问题。然而，它的解决方案并不是我所期望的。我一直在寻找一种嵌入了二进制搜索 的解决方案，这可能会降低时间复杂度。

A good solution关于给定一个键，如何使用二进制搜索找到排序数组中大于键的第一个元素。

Answer 1

您可以根据输入创建一个累积数组，其中 B[i] = A[0] + A[1] + ... + A[i]。在1和sum(A)之间生成一个随机整数x，然后二分查找B寻找第一个不小于x<的元素.

这是 Python 中的一个示例(使用 Python 的 bisect 模块，这本质上是一个二进制搜索)。

import random, bisect, collections

def make_random(A):
    s = sum(A)
    B = list(A)
    for i in xrange(1, len(B)):
        B[i] += B[i-1]
    def fn():
        r = random.randint(1, s)
        return bisect.bisect_left(B, r)
    return fn

rnd = make_random([1,4,2,3])

c = collections.Counter()
for i in xrange(10000):
    c[rnd()]+=1

print c

结果如下:

Counter({1: 3960, 3: 3036, 2: 1992, 0: 1012})