题目描述
Shuffle a set of numbers without duplicates.
Example1:
// 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();
解题思路
- 我们遍历数组每个位置，每次都随机生成一个坐标位置，然后交换当前遍历位置和随机生成的坐标位置的数字，这样如果数组有n个数字，那么我们也随机交换了n组位置，从而达到了洗牌的目的
- 这里需要注意的是i + rand() % (res.size() - i)不能写成rand() % res.size()，虽然也能通过OJ，但是那种写法不是真正的随机分布，应该使用Knuth shuffle算法
class Solution {
public:
Solution(vector<int>& nums) {
v = nums;
}
/** Resets the array to its original configuration and return it. */
vector<int> reset() {
return v;
}
/** Returns a random shuffling of the array. */
vector<int> shuffle() {
vector<int> res(v);
for(int i = 0; i < res.size(); i++){
// int t = rand() % res.size();
int t = i + rand() % (res.size() - i);
swap(res[i], res[t]);
}
return res;
}
private:
vector<int> v;
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* vector<int> param_1 = obj->reset();
* vector<int> param_2 = obj->shuffle();
*/
