A intern 面经

raychainmah 发表于 2013-1-31 11:53
一直再想这个问题，想要证明概率想等，最后看时间不多就整了个用rand取index然后用个flag数组纪录index是 ...

想了想，大概可以这么做：
for i from 0 to input.length
    j = random number between i and n
    swap input input[j]

这样每个数都有相等的机会换到这个数组的任意位置。
时间复杂度如果生成随机数是O(1) , 那么总共应该就是O(n)了
这种题还真没见过啊。。。看来我见的题还只是冰山一角。。。

transcendence 发表于 2013-1-31 13:36
想了想，大概可以这么做：
for i from 0 to input.length
    j = random number between i and n

思路大概是这样的了。不过从N到1这个逆序比较好写。能保证每个数的概率都是1/n

第三题我考虑也可以这样写：
for i in range(0, n):
    swap(a[i], a[rand(i+1, n)])

证明：
第 k 个元素 a[k-1] 被放到位置 i (0 indexed) 的概率 = (n-1)/n * (n-2)/(n-1) * ... * (n-i)/(n-i+1) * 1/(n-i) = 1/n