384.|384. Shuffle an Array

Shuffle a set of numbers without duplicates.
Example:

// Init an array with set 1, 2, and 3. int[] nums = {1,2,3}; Solution solution = new Solution(nums); // Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned. solution.shuffle(); // Resets the array back to its original configuration [1,2,3]. solution.reset(); // Returns the random shuffling of array [1,2,3]. solution.shuffle();

【384.|384. Shuffle an Array】一刷
题解:类似于蓄水池算法
如果是第i个数字,有1/i的几率被留下。保证每个数字出现在每个位置的几率相同。
class Solution { private int[] nums; private Random random; public Solution(int[] nums) { this.nums = nums; random = new Random(); }/** Resets the array to its original configuration and return it. */ public int[] reset() { return nums; }/** Returns a random shuffling of the array. */ public int[] shuffle() { if(nums == null) return null; int[] a = nums.clone(); for(int j = 1; j < a.length; j++) { int i = random.nextInt(j + 1); swap(a, i, j); } return a; }private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = 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(); */

    推荐阅读