Shuffle an Array (水塘抽樣)
隨機(jī)性問(wèn)題
水塘抽樣算法可保證每個(gè)樣本被抽到的概率相等
使用場(chǎng)景:從包含n個(gè)項(xiàng)目的集合S中選取k個(gè)樣本,其中n為一很大或未知的數(shù)量,尤其適用于不能把所有n個(gè)項(xiàng)目都存放到主內(nèi)存的情況
Knuth洗牌算法
拿起第i張牌時(shí),只從它前面的牌隨機(jī)選出j,或從它后面的牌隨機(jī)選出j交換即可
1 class Solution { 2 public: 3 Solution(vector<int>& nums) { 4 v = nums; 5 } 6 7 /** Resets the array to its original configuration and return it. */ 8 vector<int> reset() { 9 return v; 10 } 11 12 /** Returns a random shuffling of the array. */ 13 vector<int> shuffle() { 14 vector<int> res = v; 15 for (int i = 0; i < res.size(); ++i) { 16 int t = i + rand() % (res.size() - i); 17 swap(res[i], res[t]); 18 } 19 return res; 20 } 21 vector<int> v; 22 }; 23 24 /** 25 * Your Solution object will be instantiated and called as such: 26 * Solution* obj = new Solution(nums); 27 * vector<int> param_1 = obj->reset(); 28 * vector<int> param_2 = obj->shuffle(); 29 */

浙公網(wǎng)安備 33010602011771號(hào)