Leetcode 384. Shuffle an Array

Gary Chiang
2 min readJul 20, 2021

--

[medium]

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 <= 200
  • -106 <= nums[i] <= 106
  • All the elements of nums are unique.
  • At most 5 * 104 calls in total will be made to reset and shuffle.

[Java] (from @2499370956)

  1. I don’t really know clone function, so I create a global variable to store original array. If I want to refresh the array, it will return the original array
  2. Using “Math.random()” function to get a random 0 < x ≤ 1 function times i +1 to avoid overflow.
  3. Swap the current new array location to somewhere else, and put the number into the new location, which we get it from Random function.
  4. step will be: assign new array -> get random factor -> swap the location

--

--

Gary Chiang
Gary Chiang

Written by Gary Chiang

CS new grad, 6 years experience related to supply chain management. Located in Bay area

No responses yet