384. Shuffle an Array（打乱数组）

水深无声 2022-07-14 01:29 204阅读 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;
    
    		}
    	}