C++ O(n) solution


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

  • 0

    Can you explain the "rand()%count == 0" part? I'm a little unsure of the reasoning behind the else block. Thanks.


  • 0
    M

    Google Reservoir Sampling, you will understand. Simpler version can be

    int pick(int target) {
        int result = 0, counter = 1;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == target) {
                if(rand() % counter == 0)result = i;
                counter++;
            }
        }
        return result;
    }

  • 1
    J

  • 0
    T

    said in C++ O(n) solution:

    if (index == -1)
    index = i;
    else {

    you don't need the if(index==-1) statement. the first number equal to target will always be selected.


Log in to reply
 

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