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.