题目

LC.384 - 打乱数组

打乱一个没有重复元素的数组。

// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();

// 重设数组到它的初始状态[1,2,3]。
solution.reset();

// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

思路

题目要求返回原值数组和乱序数组，前者用的是 Java 深拷贝 clone()，而后者用的是洗牌算法，大概的意思就是：

• 对于一个长度为 len 的数组，每次从 len 从随机选出一个元素与最后一个元素交换，len --
• 如此直到 len 长度为 1

这样的思路经过数学证明，是完美随机打乱的

import java.util.Random;

class Solution {

    int[] origin;
    int[] shuff;

    public Solution(int[] nums) {
        this.origin = nums;
        this.shuff = nums.clone();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return origin;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for (int i = shuff.length - 1; i > 0; i--) {
            int randIndex = new Random().nextInt(i + 1);
            swap(shuff, i, randIndex);    
        }
        return shuff;
    }

    private void swap(int[] nums, int l, int r) {
        int t = nums[l];
        nums[l] = nums[r];
        nums[r] = t;
    }

}

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

总结

奇安信一面手撕了这道题，Java 自带的随机是伪随机的，任何的随机实现都是伪随机的，而洗牌算法可以让随机更 “随机” 些，想起公司年会抽奖，前辈是直接调的 Random 类，但实际上这是非随机的，应该使用洗牌算法