LeetCode 519. Random Flip Matrix中碰到了如何随机地挑选矩阵中的一个元素的问题。实际上这题目的思路并不难想。

原始算法

• step1:生成从0到所剩元素个数之间的随机数$k$；
• step2:从头开始开始遍历，找到第$k$个尚未取出的随机数，将该数取出，并将剩余元素的数量减一
• step3:重复step1,step2，直至所有元素均取出

首先，所有元素被取出均是服从均匀分布的。但是，该算法的时间复杂度是$O(n^{2})$。

改进算法

有没有时间复杂度为$O(n)$的呢？Modern algorithm of Fisher-Yates shuffle的时间复杂度就是$O(n)$的。

• step1:生成从0到所剩元素个数之间的随机数$k$；
• step2:将第k个数取出，并最后一个剩余元素与取出的元素交换，然后剩余元素的数量减一
• step3:重复step1,step2，直至所有元素均取出

通过将取出元素与剩余的最后一个元素交换，总是可以保证生成随机数$k$所对应位置的元素时尚未取出的。同样可以保证元素的取出是服从均匀分布，且算法的时间复杂度为$O(n)$。

在LeetCode 519中，还需要返回取出元素的下标，那就需要一个哈希表来记录交换元素的原始下标了。