384. Shuffle an Array

class Solution {
    private int[] array;
    private int[] original;
    private Random rand;

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

    public int[] reset() {
        array = original;
        return original = original.clone();
    }

    public int[] shuffle() {
        int[] ans = array;
        for (int i = 0; i < ans.length; i++) {
            int selectedIdx = rand.nextInt(ans.length - i) + i;
            swap(ans, i, selectedIdx);
        }
        return ans;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

这个shuffle的思路着实没想到. 思路就是给每个位置挑元素, 被挑过的在之后的位置就不能再被选了. 比如第0个位置, 从所有的元素中挑一个, 然后和此时在第0个位置的元素swap一下, 从而让被挑`选到的元素放在第0个位置. 然后给第1个位置挑元素, 那么此时在第0个元素位置的元素就不能参与了, 我们要在1到array.length - 1这个范围再挑一个元素放到第1个位置. 大致就是这个思路.

时间复杂度: O(n) shuffle的时候要遍历每个位置.
空间复杂度: O(n) 我们用额外的数组存了一开始初始的时候给我们的数组.