🌕🌗 384. 打乱数组

难度: 🌕🌗

问题描述

---

解法

class Solution {
    // 思路：
    // 假设数组元素个数 len == 3，那么一共有 3! 种排列，每个排列的概率为 1/3! = 1/3 * 1/2 * 1
    // 即，每次从剩余可选情况中选择一个下标，作为当前下标所在值的期望下标，然后删除该下标，继续从剩余下标集合中选取下一个期望下标
    // 一个优化的点是，通过将最后一个下标元素移到期望下标，再删除最后一个下标，从而降低复杂度
    int[] array;
    int[] orig;
    int len;
    Random rand;

    public Solution(int[] nums) {
        len = nums.length;
        array = new int[len];
        orig = new int[len];
        for(int i = 0; i < len; i ++) {
            orig[i] = nums[i];
        }
        rand = new Random();
    }
    
    public int[] reset() {
        return orig;
    }
    
    public int[] shuffle() {
        for(int i = 0; i < len; i ++) {
            array[i] = orig[i]; // 不能直接 array = orig 这样修改 array 后，orig 也发生了修改
        }
        int[] res = new int[len];
        int count = len;
        for(int i = 0; i < len; i ++) {
            int index = rand.nextInt(count); // [0, count)
            res[i] = array[index];
            // 如果不是 count - 1 则需要将最后一个下标元素值替换到这里
            if(index != count - 1) {
                array[index] = array[count - 1];
            }
            count --;
        }
        return res;
    }
}

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

---

输出