水塘抽样

题目	难度
382. 链表随机节点	中等
398. 随机数索引	中等
497. 非重叠矩形中的随机点	中等	TODO
519. 随机翻转矩阵	中等	TODO

定义

蓄水池抽样是一系列的随机算法，其目的在于从包含 n 个项目的集合 S 中选取 k 个样本，其中 n 为一很大或未知的数量，尤其适用于不能把所有 n 个项目都存放到内存的情况。

382. 链表随机节点

import java.util.Random;

public class Solution382 {
    static class Solution {
        private final ListNode head;
        private final Random random;

        public Solution(ListNode head) {
            this.head = head;
            this.random = new Random();
        }

        public int getRandom() {
            int i = 1;
            int ans = 0;
            for (ListNode node = head; node != null; node = node.next) {
                // 1/i 的概率选中（替换为答案）
                if (random.nextInt(i) == 0) {
                    ans = node.val;
                }
                i++;
            }
            return ans;
        }
    }
}

398. 随机数索引

import java.util.Random;

public class Solution398 {
    static class Solution {
        private final int[] nums;
        private final Random random;

        public Solution(int[] nums) {
            this.nums = nums;
            this.random = new Random();
        }

        public int pick(int target) {
            int ans = 0;
            for (int i = 0, cnt = 0; i < nums.length; ++i) {
                if (nums[i] == target) {
                    // 第 cnt 次遇到 target
                    cnt++;
                    if (random.nextInt(cnt) == 0) {
                        ans = i;
                    }
                }
            }
            return ans;
        }
    }
}

（全文完）