随机算法

Shuffle an Array

洗牌算法流程：

• 遍历每个i，随机从i和i后面区间里面取一个数，和i交换
• index = [i, n - 1]闭区间， 所有每个元素有留在原地的可能性！

原理类似于一群人在一个黑箱子里面抽彩票，每次迭代相当于一个人开始抽奖，每次抽奖的范围是index = 箱子里面所有剩下的彩票数，数量依次递减。但最后虽然每个人抽奖的彩票数量不同，但是概率是相同的。

public class Solution {

    int[] original;
    Random rand;

    public Solution(int[] nums) {
        original = nums;
        rand = new Random();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return original;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int[] nums = Arrays.copyOf(original, original.length);

        for(int i = 0; i < nums.length; i++) {
            // 在n - i ~ n 之间选一个index
            int index = rand.nextInt(nums.length - i) + i;

            int temp = nums[index];
            nums[index] = nums[i];
            nums[i] = temp;
        }

        return nums;
    }
}

考点： 是否了解洗牌算法 抽样空间是[i, n - 1]