384. Shuffle an Array（打乱数组）-蒲公英云

384. Shuffle an Array（打乱数组）

水深无声 2022-07-14 01:29 300阅读 0赞

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

题目大意：打乱一个数组，要求在打乱之后，产生的各种结果出现的概率都是相同的。例如原数组为{1,2,3}，那么打乱后结果为{1,2,3}，{1,3,2}，{2,1,3}，{2,3,1}，{3,2,1}，{3,1,2}的概率各为 1/6。

解题思路：

使用一个数组 orgn[] 用于保存数组的原始顺序，另一个数组 cur[] 用于工作。

构造方法：给 orgn[] 赋值；

reset方法：返回 orgn[] 数组；

shuffle方法：先用 orgn[] 数组初始化 cur[] 数组，然后从右往左遍历 cur[] 数组，即cur[i]，i 从 len-1 到 0，对于cur[i] ，任何 cur[j]，（j<=i），cur[j] 都有 1/(i+1)的可能性与cur[i] 进行交换。代码如下：（250ms，beats 70.73%）

public class Solution {
        private int[] orgn;
        private int[] cur;
        public Solution(int[] nums) {
            orgn = nums;
        }
        /** Resets the array to its original configuration and return it. */
        public int[] reset() {
            return orgn;
        }
        /** Returns a random shuffling of the array. */
        public int[] shuffle() {
            int len = orgn.length;
            cur = new int[len];
            for(int i=0;i<len;i++)
                cur[i] = orgn[i];
            int pos;//记录要交换元素的位置
            int temp; //记录要交换的值
            Random ran = new Random();
            for(int i=len-1;i>=0;i--){
                pos = ran.nextInt(i+1);
                temp = cur[pos];
                cur[pos] = cur[i];
                cur[i] = temp;
            }
            return cur;
        }
    }