LeetCode384_打乱数组

2019-12-05

用python语言解答LeetCode的384题

方法一： Fisher-Yates洗牌算法

算法：
Fisher-Yates洗牌算法跟暴力算法很像。在每次迭代中，生成一个范围在当前下标到数组末尾下标之间的随机整数。
接下来，将当前元素和随机选出的下标所指的元素相互交换。

注：当前元素是可以和它本身互相交换的-否则生成最后的排列组合的概率就不对了。

用官方题解的洗牌法会报错，研究了一下，评论区有位大佬分析的很中肯

采用随机数会报错

因为随机数算法是根据种子来计算出随机值，再把随机值作为新种子算下一个随机数，也就是说相同的种子算出来的随机数是相同的，然后每次shuffle的时候都把随机数种子设置为0，然后每次随机的结果都是相同的，所以每次shuffle的结果是相同的。

有人说随机数一秒内的结果是一样的，是因为他在update中把当前时间设为随机数种子，时间以秒计的情况下当然1秒内的时间是相同的，所以1秒内的随机数结果当然也是相同的。
一般来说一个程序只要在初始阶段把当前时间设置为随机数即可保证随机性，之后都不用再设置随机数种子了。

然后人生苦短，愉快的当个调包侠之后通过啦~~~

代码实现：


    #coding:utf-8

    import random

    class Solution:

        def __init__(self, nums: List[int]):
            self.list_backup = list(nums)
            self.nums = nums

        def reset(self) -> List[int]:
            """
            Resets the array to its original configuration and return it.
            """
            self.nums = list(self.list_backup)
            return self.nums


        def shuffle(self) -> List[int]:
            """
            Returns a random shuffling of the array.
            """
            random.shuffle(self.nums)
            return self.nums


    # Your Solution object will be instantiated and called as such:
    # obj = Solution(nums)
    # param_1 = obj.reset()
    # param_2 = obj.shuffle()

Reference：

1.官方题解
https://leetcode-cn.com/problems/shuffle-an-array/solution/da-luan-shu-zu-by-leetcode/