Sample Offline

EPI

Description:

Given an array of integers, return a random subset of k randome integers. Use as few calls to random() as possible. All subsets should be equally likely.

Example:

Note

Idea:

类似random shuffle; input arr 需要被shuffle，然后当前值进到result里。

Code:

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

using namespace std;

vector<int> randomSubsetOffline(vector<int> nums, int k) {
    if(nums.empty() || k>nums.size() ) return vector<int>();
    vector<int> result;
    result.reserve(k);

    int mv_len=result.size();

    for (int i=0; i<k; i++){
        int randLen = nums.size()-i;
        int randIndx = rand()%randLen + i;
        swap(nums[i], nums[randIndx]);
        result.push_back(nums[i]);
    }

    return result;
}

int main(){

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

    for(auto elem: andomSubsetOffline(arr,4)){
        cout<<elem<<' ';
    }

}