Question

Formatted question description: https://leetcode.ca/all/384.html

 384	Shuffle an Array

 Shuffle a set of numbers without duplicates.

 Example:

 // Init an array with set 1, 2, and 3.
 int[] nums = {1,2,3};
 Solution solution = new Solution(nums);

 // Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
 solution.shuffle();

 // Resets the array back to its original configuration [1,2,3].
 solution.reset();

 // Returns the random shuffling of array [1,2,3].
 solution.shuffle();

Algorithm

Traverse each position of the array, randomly generate a coordinate position each time, and then exchange the number of the current traverse position and the randomly generated coordinate position.

If the array has n numbers, then we also randomly exchange n sets of positions, thus achieving the purpose of shuffling.

It should be noted here that i + rand()% (res.size()-i) cannot be written as rand()% res.size().

Code

Java

• Java
• C++
• Python

• import java.util.ArrayList;
  import java.util.List;
  import java.util.Random;
  
  public class Shuffle_an_Array {
  
      // 1. array deep copy
      // 2. random.nextInt to dynamic list size
      class Solution {
          private int[] array;
          private int[] original;
  
          private Random rand = new Random();
  
          private List<Integer> getArrayCopy() {
              List<Integer> asList = new ArrayList<Integer>();
              for (int i = 0; i < array.length; i++) {
                  asList.add(array[i]);
              }
              return asList;
          }
  
          public Solution(int[] nums) {
              array = nums;
              original = nums.clone();
          }
  
          public int[] reset() {
              array = original;
              original = original.clone();
              return array;
          }
  
          public int[] shuffle() {
              List<Integer> aux = getArrayCopy();
  
              for (int i = 0; i < array.length; i++) {
                  int removeIdx = rand.nextInt(aux.size());
                  array[i] = aux.get(removeIdx);
                  aux.remove(removeIdx);
              }
  
              return array;
          }
      }
  /**
   * Your Solution object will be instantiated and called as such:
   * Solution obj = new Solution(nums);
   * int[] param_1 = obj.reset();
   * int[] param_2 = obj.shuffle();
   */
  }
  

• // OJ: https://leetcode.com/problems/shuffle-an-array/
  // Time:
  //      Solution: O(N)
  //      reset: O(1)
  //      shuffle: O(N)
  // Space: O(N)
  class Solution {
  private:
      vector<int> nums;
  public:
      Solution(vector<int> nums) : nums(nums) {}
      
      vector<int> reset() {
          return nums;
      }
      
      vector<int> shuffle() {
          vector<int> ans(nums);
          for (int i = nums.size(); i > 1; --i) {
              int j = rand() % i;
              swap(ans[i - 1], ans[j]);
          }
          return ans;
      }
  };
  

• class Solution(object):
  
    def __init__(self, nums):
      """
  
      :type nums: List[int]
      :type size: int
      """
      self.nums = nums
      self.reset = lambda: self.nums
  
    def shuffle(self):
      """
      Returns a random shuffling of the array.
      :rtype: List[int]
      """
      nums = self.nums + []
      for i in reversed(range(0, len(nums))):
        idx = random.randrange(0, i + 1)
        nums[i], nums[idx] = nums[idx], nums[i]
      return nums
  
  # Your Solution object will be instantiated and called as such:
  # obj = Solution(nums)
  # param_1 = obj.reset()
  # param_2 = obj.shuffle()
  
  

All Problems

All Solutions