Sponsored
The Fisher-Yates shuffle algorithm, also known as the Knuth shuffle, is an efficient algorithm for generating a random permutation of a finite sequence. The algorithm works by iterating backward through the array and swapping each element with a randomly selected element from the portion of the array that has not been shuffled yet.
Time Complexity: O(n) for both reset and shuffle functions.
Space Complexity: O(n) for maintaining a copy of the original array.
1class Solution {
2 constructor(nums) {
3 this.original = nums.slice();
4 this.array = nums.slice();
5 }
6
7 reset() {
8 this.array = this.original.slice();
9 return this.array;
10 }
11
12 shuffle() {
13 for (let i = this.array.length - 1; i > 0; i--) {
14 let j = Math.floor(Math.random() * (i + 1));
15 [this.array[i], this.array[j]] = [this.array[j], this.array[i]];
16 }
17 return this.array;
18 }
19}In JavaScript, 'slice()' is used to copy the array. The 'shuffle' method uses the Fisher-Yates algorithm to swap elements randomly. The 'reset' simply returns a fresh copy of the original array.
This approach involves generating a permutation recursively by picking an element and placing it at different positions. This is less efficient than the Fisher-Yates method and not suitable for large arrays.
Time Complexity: O(n!) because it attempts every permutation recursively.
Space Complexity: O(n) for maintaining the array copy.
1class Solution {
2 constructor(nums)
In JavaScript, this solution uses recursion to generate permutations, not fully efficient nor strictly generating permutations but a form of randomized shuffle which is recursive, ensuring all elements are possibly swapped.