LC 384


Solution to LeetCode 384 Shuffle an Array.

LeetCode 384

Shuffle an Array (Medium). [link]

“Fisher-Yates” Algorithm for shuffling. The probability of selecting one from N elements is 1/n. Assume the selected one element had not been selected, the probability to select one from the remaining (n-1) elements is ((n-1)/n) * (1/(n-1)) = 1/n, etc.

class Solution(object):

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

    def reset(self):
        """
        :rtype: List[int]
        """
        return self.nums

    def shuffle(self):
        """
        :rtype: List[int]
        """
        self.tmp = list(self.nums)
        for i in range(len(self.tmp)):
            j = random.randrange(i, len(self.tmp))
            self.tmp[i], self.tmp[j] = self.tmp[j], self.tmp[i]
        return self.tmp

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

Note: Randomly select a number in a range: random.randint(a,b), a inclusive and b inclusive. random.randrange(a,b), a inclusive and b exclusive.


  TOC