Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.
Implement the Solution class:
Solution(int[] nums) Initializes the object with the integer array nums.int[] reset() Resets the array to its original configuration and returns it.int[] shuffle() Returns a random shuffling of the array.
Example 1:
Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // Shuffle the array [1,2,3] and return its result.
// Any permutation of [1,2,3] must be equally likely to be returned.
// Example: return [3, 1, 2]
solution.reset(); // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle(); // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]
Constraints:
1 <= nums.length <= 50-106 <= nums[i] <= 106nums are unique.104 calls in total will be made to reset and shuffle.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.
In the C implementation, we first allocate memory for the 'Solution' structure. We perform a deep copy of the input array for both the 'original' and 'array' members of the structure. The 'reset' function restores the 'array' to its original configuration, while the 'shuffle' function uses the Fisher-Yates algorithm to shuffle the 'array'. We clean up memory in 'solutionFree'.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) for both reset and shuffle functions.
Space Complexity: O(n) for maintaining a 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.
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.
JavaScript
Time Complexity: O(n!) because it attempts every permutation recursively.
Space Complexity: O(n) for maintaining the array copy.
| Approach | Complexity |
|---|---|
| Fisher-Yates Shuffle Algorithm | Time Complexity: O(n) for both reset and shuffle functions. |
| Recursive Permutation Generation | Time Complexity: O(n!) because it attempts every permutation recursively. |
Shuffle the Array (Constant Space) - Leetcode 1470 - Python • NeetCodeIO • 19,611 views views
Watch 9 more video solutions →Practice Shuffle an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor