C++ 蓄水池算法

admin1

蓄水池算法
对于一个未知大小的数据流，随机取k个数据，要求选取的概率相等；
证明：1 先按顺序取k个数 ，每个数都是1/i，i从1到k；
2 然后在第 k+1 个数时，以 k / (k+1) 的概率决定替换；
3 随机选择先前池子中的一个数，与第k+1 个数进行替换，即 1/k * k/(k+1) = 1/(k+1);
最终保证 每个数 都是 以 1/n 的概率选取；

struct ListNode {
    int val;
    ListNode* next;
    ListNode():val(0),next(nullptr){}
    ListNode(int x) :val(x), next(nullptr) {}
};

int main()
{
    ListNode* head = new ListNode(1);
    ListNode* node = head;
    int n = 100, k = 10;
    for (int i = 2; i < n; i++) {
        ListNode* tmp = new ListNode(i);
        node->next = tmp;
        node = node->next;
    }

    vector<int> res;
    for (int i = 0; i < k; i++) {
        res.push_back(head->val);
        head = head->next;
    }
    int i = k;
    while(head){
        int r = rand() % (i+1);
        if (r < k) {
            res[rand() % k] = head->val;
        }
        head = head->next;
        i++;
    }

    for (auto x : res) cout << x << " ";
    return 0;
}