The problem involves designing a class that can shuffle an array of integers and reset it to its original state. The class should support two main operations:
The challenge is to shuffle the array in a way that all permutations of the array are equally likely, simulating a fair shuffle.
Shuffling an array requires a random and unbiased process to rearrange elements. The Fisher-Yates algorithm is a widely recognized method for generating random permutations, which ensures that each possible permutation of the array is equally likely. For resetting, we simply store a copy of the original array and restore it when needed.
n
is the number of elements in the array, as it copies the array.reset()
function also runs in O(n) since it returns a copy of the original array.shuffle()
function runs in O(n) as it iterates through the array once and performs constant-time operations for each element.class Solution {
private:
std::vector<int> nums;
std::vector<int> original;
public:
Solution(std::vector<int>& nums) : nums(nums), original(nums) {}
std::vector<int> reset() {
nums = original; // Restore to the original array
return nums;
}
std::vector<int> shuffle() {
std::vector<int> shuffled = nums;
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(shuffled.begin(), shuffled.end(), g);
return shuffled;
}
};
class Solution:
def __init__(self, nums: list[int]):
self.nums = nums
self.original = nums[:]
def reset(self) -> list[int]:
return self.original
def shuffle(self) -> list[int]:
shuffled = self.nums[:]
for i in range(len(shuffled) - 1, 0, -1):
j = random.randint(0, i)
shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
return shuffled
class Solution {
private int[] nums;
private int[] original;
private Random rand = new Random();
public Solution(int[] nums) {
this.nums = nums;
this.original = nums.clone();
}
public int[] reset() {
nums = original.clone(); // Reset to the original array
return nums;
}
public int[] shuffle() {
int[] shuffled = nums.clone();
for (int i = shuffled.length - 1; i > 0; i--) {
int j = rand.nextInt(i + 1);
int temp = shuffled[i];
shuffled[i] = shuffled[j];
shuffled[j] = temp;
}
return shuffled;
}
}
/**
* @param {number[]} nums
*/
var Solution = function (nums) {
this.nums = nums;
this.original = nums.slice();
};
/**
* @return {number[]}
*/
Solution.prototype.reset = function () {
return this.original;
};
/**
* @return {number[]}
*/
Solution.prototype.shuffle = function () {
const shuffled = this.nums.slice();
for (let i = shuffled.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
}
return shuffled;
};