320. Shuffle an Array
Design a class Solution that is constructed with an integer array nums and an integer seed, and supports two operations, each returning the array's contents afterwards:
reset()— restore the array to its original order.shuffle()— rearrange the current contents into a pseudo-random permutation.
The judge pins the randomness so results are checkable. Keep an integer state initialized to seed; a draw in the range 0 … m − 1 is: first update state = (state × 1103515245 + 12345) mod 2³¹, then the drawn value is state mod m. shuffle() must perform exactly one modern Fisher–Yates pass over the current array a of length n:
for i from n − 1 down to 1: j = draw(i + 1), then swap a[i] and a[j].
reset() restores the original values but never touches state — only the draws inside shuffle() advance it, and the state carries over across calls.
Example 1:
Input: nums = [1, 2, 3], seed = 42, then shuffle(), reset(), shuffle()
Output: [2, 3, 1], then [1, 2, 3], then [2, 1, 3]
Explanation: The first shuffle draws j = 0 (swap positions 2,0) then j = 0 (swap positions 1,0), producing [2, 3, 1]. reset restores [1, 2, 3] without consuming draws, so the second shuffle continues from the state the first one left behind.
Example 2:
Input: nums = [7, 9], seed = 5, then shuffle(), shuffle(), reset()
Output: [9, 7], then [9, 7], then [7, 9]
Explanation: With two elements each shuffle makes exactly one draw with i = 1. The first draw gives j = 0, swapping the pair into [9, 7]; the second gives j = 1, which swaps a[1] with itself and changes nothing. reset then restores the original [7, 9].
Constraints:
- 1 ≤ nums.length ≤ 1000
- -10⁶ ≤ nums[i] ≤ 10⁶
- 0 ≤ seed < 2³¹
- 1 ≤ q ≤ 100 operations
- The product state * 1103515245 exceeds 32 bits — use 64-bit arithmetic.
Hints:
Keep two arrays: a frozen copy of the original for reset(), and a working array that shuffles mutate. Copy defensively — aliasing the two is the classic bug.
Write one helper draw(m) exactly as specified; Fisher–Yates is then four lines: loop i from n − 1 down to 1, j = draw(i + 1), swap a[i] with a[j]. The i + 1 (not n) in the draw is what makes every permutation reachable exactly once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3], seed = 42, ops = [shuffle, reset, shuffle]
Expected output: [2, 3, 1], [1, 2, 3], [2, 1, 3]