概率问题，蓄水池抽样与生成随机数都可以解决。蓄水池抽样适合数据量巨大且不知道数组集合大小时的随机抽样，因为是线性扫描每一个元素进行抽样，空间复杂度为 O(1) ,时间复杂度为O(n)。
蓄水池抽样算法：
class Solution { ListNode head; Random random; public Solution(ListNode head) { this.head = head; random = new Random(0); } public final int getRandom() { Integer an = null; int point = 1; ListNode node = head; while (node != null) { if (an == null) { an = node.val; } else { int ran = random.nextInt(point); if (ran < 1) { an = node.val; } } node = node.next; point++; } return an == null ? 0 : an; } }
随机数抽样，需要预先知道集合大小：
class Solution { private ListNode head = null; private int size = 0; Random random = new Random(0); public Solution(ListNode head) { if (head != null) { this.head = head; ListNode node = head; while (node != null) { node = node.next; this.size++; } } } /** * Returns a random node‘s value. */ public final int getRandom() { if (size <= 1) { return head.val; } int currentRandom = random.nextInt(size); return getNode(currentRandom).val; } private final ListNode getNode(int point) { if (point >= this.size) { return null; } ListNode an = head; while (point > 0) { an = an.next; point--; } return an; } }
JS 蓄水池算法：
var Solution = function (head) { this.head = head; }; /** * Returns a random node‘s value. * @return {number} */ Solution.prototype.getRandom = function () { let point = 1; let an = -1; let node = this.head; while (node != null) { if (an == -1) { an = node.val; } else { let ran = parseInt(Math.random() * (point)); if (ran < 1) { an = node.val; } } node = node.next; point++; } return an; };
原文：https://www.cnblogs.com/niuyourou/p/13593905.html