0384._Shuffle_an_Array.md

384. Shuffle an Array

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/shuffle-an-array/

内容描述

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

解题方案

思路 1 ******- 时间复杂度: O(N) + O(N) + O(N^2) - 空间复杂度: O(N)

randrange是个好函数，beats 40.58%

class Solution:

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.array = nums[:]
        self.original = nums[:]
        

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

    def shuffle(self):
        """
        Returns a random shuffling of the array.
        :rtype: List[int]
        """
        tmp = self.array[:]
        for i in range(len(self.array)):
            remove_idx = random.randrange(len(tmp))
            self.array[i] = tmp.pop(remove_idx)
        return self.array

思路 2 ******- 时间复杂度: O(N) + O(N) + O(N) - 空间复杂度: O(N)

这就是洗牌算法吧，洗牌算法几种常见的：

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结果，比如他没有抽中 → 那么概率就会变。

beats 26.17%

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]
        """
        res = self.lst[:]
        for i in range(len(res) - 1, 0, -1):
            j = random.randint(0, i)
            res[i], res[j] = res[j], res[i]
        return res