LC 384. Shuffle an Array

标签：arr Shuffle nums int 384 frac Array public neq

384. Shuffle an Array

---

思路与题解

按照post[1]中的解释，这么想这个问题：第一次抽牌中，\(k\) 没被抽中的概率为：

\[P(A_{1} \neq k) = \frac{n-1}{n} \]

第二次抽牌，\(k\) 被抽中的概率为：

\[P(A_{2} = k, A_{1} \neq k) = P(A_{2} = k | A_{1} \neq k) P(A_{1} \neq k) \]

即为：

\[P(A_{2} = k, A_{1} \neq k) = \frac{1}{n-1} * \frac{n-1}{n} = \frac{1}{n} \]

以此类推。

class Solution {
    private int[] originalNums;
    private int[] nums;
    private Random rand;

    public void exch(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public Solution(int[] nums) {
        this.originalNums = nums.clone();
        this.nums = nums.clone();
        rand = new Random();
    }

    public int[] reset() {
        return originalNums;
    }

    public int[] shuffle() {
        for (int i = nums.length - 1; i >= 0; i--) {
            int j = rand.nextInt(i+1);
            exch(nums, i, j);
        }

        return nums;
    }
}

References

[1] First Accepted Solution - Java

[2] Fisher–Yates shuffle 洗牌算法

标签：arr,Shuffle,nums,int,384,frac,Array,public,neq
From： https://www.cnblogs.com/GradientBoosted/p/17125292.html