Tag Archives: shuffle

LeetCode Shuffle an Array

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。]]>