C++ O(n) 8 lines uisng Reservoir Sampling


  • 1
    class Solution {
    private:
        vector<int> nums;
        
    public:
        Solution(vector<int> nums) {
            this->nums = nums;
            srand(time(0));
        }
        
        int pick(int target) {
            int ans;
            
            for (int i = 0, cnt = 1; i < nums.size(); i++) {
                if (nums[i] == target && ((rand() % cnt++) == 0)) { ans = i; }
            }
            
            return ans;
        }
    };
    

  • 0
    H

    That's really clever.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.