本文主要是介绍给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
答案来自网络： 蓄水池抽样：先保存前k个元素， 从第k+1个元素开始， 以1/i (i=k+1, k+2,…,N) 的概率选中第i个元素，并随机替换掉一个已保存的记录，这样遍历一次得到k个元素，可以保证完全随机选取。
这篇关于给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
