Sample Online

Description:

Given a stream of input numbers, design an algorithm that reads an integer at a time and maintains a random sampling of k integers.

Example:

Note

Idea:

1) Create an array reservoir[0..k-1] and copy first k items of stream[] to it. 2) Now one by one consider all items from (k+1)th item to nth item. …a) Generate a random number from 0 to i where i is index of current item in stream[]. Let the generated random number is j. …b) If j is in range 0 to k-1, replace reservoir[j] with arr[i]

原因：第i个num有k/i概率被选中，选中后，已有的k个中的每一个都有1/k概率被剔除

Code:

模拟streaming

#include <vector>
#include <iostream>
#include <cstdlib>

using namespace std;

vector<int> randomSubsetOnline(vector<int> nums, int k) {
    if(nums.empty() || k>nums.size() ) return vector<int>();
    vector<int> result(nums.begin(), nums.begin()+k);

    for(int i=k; i<nums.size(); ++i){
        int randLen=k+1;
        int j = rand()%randLen;
        if(j<k){
            swap(result[j], nums[i]);
        }
        for(auto elem: result){
            cout<<elem<<' ';
        }
        cout<<endl;
    }

    return result;
}

int main(){
    vector<int> arr={1,2,3,4,5,6,7,8,9,10};

    randomSubsetOnline(arr,3);
}