Shuffle an Array

这题因为Python的随机模块里面就有shuffle函数，算是作弊了，另外毛子还用了sample取样也是一样的思路，如果真要自己实现shuffle，想到的办法还是随机取下标然后输出的办法

class Solution(object):

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

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

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


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

上面的方法纯粹靠Python的库函数取巧，真正实现随机打散的话，就是利用一个随机算法里面很常用的技巧，即随机选下标，然后加该下标的元素移到数组尾部同时减小随机范围，这样就能实现等概率打散数组

class Solution(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.baseNums = nums
        self.n = len(nums)

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

    def shuffle(self):
        """
        Returns a random shuffling of the array.
        :rtype: List[int]
        """
        end = self.n
        result = []
        tmpNums = self.baseNums[:]
        for i in xrange(end):
            tmp = random.randint(0, end - i - 1)
            tmpNums[tmp], tmpNums[end - i - 1] = tmpNums[end - i - 1], tmpNums[tmp]
            result.append(tmpNums[end - i - 1])
        return result