Skip to content

384 Shuffle an Array

384. Shuffle an Array

题目: https://leetcode.com/problems/shuffle-an-array/

难度 : Medium

思路:

这就是洗牌算法吧,洗牌算法几种常见的:

http://www.cnblogs.com/tudas/p/3-shuffle-algorithm.html

http://www.matrix67.com/blog/archives/879

也是有wikipedia page的: https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

最简单的算法是很容易想到的, O(N^2)

然后就是modern 算法:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

这个感觉还是比较容易证明的,一开始生成的数字 1/n 概率

没选中,下一个 n-1 /n * 1/ n-1 = 1/n, 所以每个位置都是等概率的?

这个有很妙的点:

比如五个人顺序抽签,只要不uncover 结果,那么就是等概率的。

但是第一个人抽奖之后uncover结果,比如他没有抽中 → 那么概率就会变。

AC代码:

class Solution(object):

    def __init__(self, nums):
        """

        :type nums: List[int]
        :type size: int
        """
        self.lst = nums


    def reset(self):
        """
        Resets the array to its original configuration and return it.
        :rtype: List[int]
        """
        return self.lst


    def shuffle(self):
        """
        Returns a random shuffling of the array.
        :rtype: List[int]
        """
        import random
        res = self.lst[:]
        n = len(res)
        for i in range(n-1,0,-1):
            j = random.randint(0,i)
            res[i], res[j] = res[j], res[i]
        return res



回到顶部