Hexo

Question

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.

Solution

Fisher-Yates洗牌算法。将数组分为两组部分，一组为已打乱的部分，一组为未打乱的部分。每次从未打乱部分中取一个元素，随机和一个未打乱部分的元素（包括自身）交换，则该位置变为已打乱的部分。

Code

class Solution {
    int[] data;
    int[] shuffle;
    Random r;
    public Solution(int[] nums) {
        data = nums;
        shuffle = new int[nums.length];
        r = new Random();
        for(int i = 0; i < data.length; i++){
            shuffle[i] = nums[i];
        }
    }
    
    public int[] reset() {
        return data;
    }
    
    public int[] shuffle() {
        for(int i = data.length-1 ; i >= 0; i--){
            swap(i, r.nextInt(i+1));
        }
        return shuffle;
    }
    
    private void swap(int i, int j){
        int temp = shuffle[i];
        shuffle[i] = shuffle[j];
        shuffle[j] = temp;
    }
}

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

Solution 2

将静态数组转换为动态数组，每次随机取动态数组里的一个index。
将其按顺序填入result数组，并删除动态数组这个位置。
最后返回result。

Code

class Solution {
    int[] data;
    Random r;
    public Solution(int[] nums) {
        data = nums;
        r = new Random();
    }
    
    public int[] reset() {
        return data;
    }
    
    public int[] shuffle() {
        ArrayList<Integer> bin = new ArrayList<>();
        for(int i = 0; i < data.length; i++){
            bin.add(data[i]);
        }
        
        int[] ret = new int[data.length];
        for(int i = 0 ; i < data.length; i++){
            int random = r.nextInt(bin.size());
            ret[i] = bin.get(random);
            bin.remove(random);
        }
        return ret;
    }
}

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