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();
 */
}

All Problems

All Solutions