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.
1import java.util.Random;
2
3class Solution {
4 private int[] original;
5 private int[] array;
6 private Random rand;
7
8 public Solution(int[] nums) {
9 original = nums.clone();
10 array = nums.clone();
11 rand = new Random();
12 }
13
14 public int[] reset() {
15 array = original.clone();
16 return array;
17 }
18
19 public int[] shuffle() {
20 for (int i = array.length - 1; i > 0; --i) {
21 int j = rand.nextInt(i + 1);
22 int temp = array[i];
23 array[i] = array[j];
24 array[j] = temp;
25 }
26 return array;
27 }
28}In the Java implementation, we use arrays and the Random class. We clone the input array to both original and array. The shuffle function implements the Fisher-Yates shuffle to randomly permute the elements.
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.