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.
1from random import randint
2
3class Solution:
In this Python solution, we recursively generate a permutation by swapping the current element with any element after it. This ensures that all permutations are equally probable, though it's less efficient for large arrays compared to Fisher-Yates.