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

题目大意：打乱一个数组，要求在打乱之后，产生的各种结果出现的概率都是相同的。例如原数组为{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;

		}
	}