
Problem Statement
In this problem, we are tasked with creating a Solution
class that manages an array of integers and allows for two main operations: shuffling and resetting. The shuffle
method should output a randomly shuffled version of the array where each permutation is equally likely, capturing the essence of true randomness without any bias towards particular arrangements. The reset
method, on the other hand, should restore the array to its original order as it was upon initialization. These operations facilitate the ability to toggle back and forth between a fixed and a randomized sequence of the array elements.
Examples
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
-10^6 <= nums[i] <= 10^6
- All the elements of
nums
are unique. - At most
10^4
calls in total will be made toreset
andshuffle
.
Approach and Intuition
Understanding the given example and the constraints outlined helps us establish an approach. Let's step through the logic:
Initialization:
- When an instance is created, the original array is stored. This can be done by maintaining a private copy of the array that remains unaltered, serving as a reference for the reset operation.
Shuffle Algorithm:
- To ensure each element has an equal probability of occupying any position in the array, we can employ the Fisher-Yates shuffle algorithm. This efficient technique works in an in-place manner by iterating through the array and swapping each element with another randomly chosen element that has not been locked into place yet. By methodically locking elements from one end of the array to another, this algorithm ensures a fair shuffle in O(n) time complexity.
Reset Operation:
- The reset operation is straightforward, where the method simply returns a copy of the initially stored array, thus ensuring the array's original order is maintained and can be recalled after any number of shuffle operations.
Performance Considerations:
- Given that the constraints allow for up to
10^4
calls in total to bothreset
andshuffle
, the implementation of both methods must be efficient. Resetting is inherently quick since it involves returning a pre-stored value. The shuffle, using Fisher-Yates, ensures that we handle each element just once per shuffle call, thereby maintaining linear time complexity, which is ideal given the potential frequency of operations.
- Given that the constraints allow for up to
Understanding this setup and approach assures us that the system will operate efficiently under the constraints stipulated, providing robust and equitable shuffling while allowing for instant resets to the baseline order.
Solutions
- Java
class Solution {
private int[] numsArray;
private int[] initialArray;
Random randomGenerator = new Random();
private int generateRandom(int low, int high) {
return randomGenerator.nextInt(high - low) + low;
}
private void exchangeIndices(int index1, int index2) {
int temp = numsArray[index1];
numsArray[index1] = numsArray[index2];
numsArray[index2] = temp;
}
public Solution(int[] nums) {
numsArray = nums;
initialArray = nums.clone();
}
public int[] reset() {
numsArray = initialArray;
initialArray = initialArray.clone();
return initialArray;
}
public int[] shuffle() {
for (int i = 0; i < numsArray.length; i++) {
exchangeIndices(i, generateRandom(i, numsArray.length));
}
return numsArray;
}
}
The provided Java code defines a solution to shuffle an array. It involves initializing, shuffling, and resetting an array to its original configuration.
- Initialize two arrays,
numsArray
andinitialArray
, whereinitialArray
stores the original configuration. - A random number generator is utilized to assist in shuffling.
- The
shuffle()
method iterates over the array, swapping each element at indexi
with an element at a random index. - In the
reset()
method, the array is reset to the original elements stored ininitialArray
.
Key methods in the solution:
generateRandom(int low, int high)
- generates a random integer between two indices.exchangeIndices(int index1, int index2)
- swaps the elements at the specified indices.reset()
- returns the array to its original state.shuffle()
- rearranges the elements in the array randomly.
Use the shuffle()
method to get a new random permutation of the array, and apply reset()
to revert to the initial configuration. This approach ensures effective shuffling while allowing the array to be easily reset when needed.
No comments yet.