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

  • 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