Fisher-Yates Algorithm

Fisher-Yates Algorithm is a random shuffle algorithm, it can be used to solve this problem.

384. Shuffle an Array

Naive solution (O(N²))

class Solution:
    def __init__(self, nums):
        self.array = nums
        self.original = list(nums)
def reset(self):
        self.array = self.original[:]
        return self.original
def shuffle(self):
        be_chosen_array = self.array[:]
        for i in range(len(self.array)):
            random_idx = random.randrange(len(be_chosen_array))
            # pop from an arbitary location has the complexity of O(n)
            self.array[i] = be_chosen_array.pop(random_idx)
        return self.array

Fisher-Yates Algorithm (O(n))

class Solution:
    def __init__(self, nums):
        self.array = nums
        self.original = list(nums)
def reset(self):
        self.array = self.original[:]
        return self.original
def shuffle(self):
        N = len(self.array)
        for i in range(N):
            j = random.randrange(N)
            # swap has the complexity of O(1), i == j is allowed.
            self.array[i], self.array[j] = self.array[j], self.array[i]
        return self.array