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

---

本题要对一个数组随机洗牌，也就是随机打乱。 第一种思路是，相当于对原数组进行无放回的随机抽样，每次从原数组中随机抽取一个数字，放到新数组中，然后在剩余数组中再随机抽样，直到抽完所有数字。 具体实现是这样的，我们先令ans=original，此时我们要从n个数中随机抽样，把随机抽到的数字放到ans的末尾；然后随机抽样的整体减1，也就是n–，从n-1个数中再随机抽样，放到ans的倒数第二个位置。所以我们令pos为随机抽到的数应该放的位置，那么此时的抽样整体长度就是pos+1，每次把抽到的数和pos处的数交换一下。 完整代码如下，注意不能自己设置随机种子，要不然会WA！ [cpp] class Solution { private: vector<int> original; public: Solution(vector<int> nums) { original = nums; } /** Resets the array to its original configuration and return it. */ vector<int> reset() { return original; } /** Returns a random shuffling of the array. */ vector<int> shuffle() { //srand(time(NULL)); // caution!! vector<int> ans = original; int pos = ans.size() – 1; while (pos > 0) { int r = rand() % (pos + 1); swap(ans[pos], ans[r]); –pos; } return ans; } }; [/cpp] 本代码提交AC，用时275MS。 还有一种思路更简单，遍历数组，对于每一位，都随机生成一个需要交换的位置，然后交换。完整代码如下： [cpp] class Solution { private: vector<int> original; public: Solution(vector<int> nums) { original = nums; } /** Resets the array to its original configuration and return it. */ vector<int> reset() { return original; } /** Returns a random shuffling of the array. */ vector<int> shuffle() { //srand(time(NULL)); // caution!! vector<int> ans = original; for (int i = 0; i < ans.size(); ++i) { int j = rand() % ans.size(); swap(ans[i], ans[j]); } return ans; } }; [/cpp] 本代码提交AC，用时269MS。]]>