每日一题-LeetCode398-随机数索引-数学-蓄水池抽样

原题链接

蓄水池抽样，实际就是产生一个 [0 ~ 抽到次数) 的随机数，如果是0那就选他，不是就不动

class Solution {
public:

    vector nums;

    Solution(vector& _nums) {
        nums = _nums;
    }
    
    int pick(int target) {
        int ans;
        for(int i = 0, cnt = 0; i < nums.size(); i ++){
            if(nums[i] == target){
                cnt ++;
                //第一次抽到一定会有个答案在这的
                if(rand() % cnt == 0)
                    ans = i;
            }
        }
        return ans;
    }
};