如何公平的洗牌
洗牌问题
洗牌,显然是一个随机算法了。随机算法还不简单?随机呗。把所有牌放到一个数组中,每次取两张牌交换位置,随机 k 次即可。
如果你的答案是这样,通常面试官会进一步问一下,k 应该取多少?100?1000?10000?
很显然,取一个固定的值不合理。如果数组中有 1000000 个元素,随机 100 次太少;如果数组中只有 10 个元素,随机 10000 次又太多。一个合理的选择是,随机次数和数组中元素大小相关。比如数组有多少个元素,我们就随机多少次。
这个答案已经好很多了。但其实,连这个问题的本质都没有触及到。此时,面试官一定会狡黠地一笑:这个算法公平吗?
我们再看问题:设计一个 公平 的洗牌算法。