[数据结构与算法]【每日一题见微知著】水塘抽样算法——未知长度随机抽取问题

??寒假新坑——代码之狐的每日做题笔记

1.16、382. 链表随机节点

题目描述：

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。

实现 Solution 类：

• Solution(ListNode head) 使用整数数组初始化对象。
• int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

解题方法：

思路一【缓存链表中的每一个节点值，通过随机数访问】

代码实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    //通过链表保存数据
    private List<Integer> list=new ArrayList<>();
    //获取长度
    int l=0;

    public Solution(ListNode head) {
        //迭代节点，保存每一个节点内容
        while(head!=null){
            list.add(head.val);
            //迭代节点
            head=head.next;
            //每保存一个数据长度加1
            l++;
        }
        
    }
    public int getRandom() {
        //获得随机数
        Random random=new Random();
        //Math.random()内部调用的方法就是Random类中的nextDouble()
        //int index=(int)(Math.random()*(max-min)+min)
        
        return list.get(random.nextInt(l));
    }
}

思路二【水塘抽样算法，由数学推导证明】

对于第i个元素，获取在0~i的随机数值r，如果r=0则选取为结果，即对于当前元素，有1/i可能成为结果——随机抽取不应该每个元素成为结果概率都是1/n吗？

这里我们还没考虑后面一个元素成为结果覆盖前一个元素的情况——最后一个成为结果概率1/n，倒数第2个元素（1/(n-1)-1/(n-1)x(1/n)=1/n)，成为结果的概率-成为结果但是被覆盖的概率=恰好为1/n…同理可证明每一个元素都有1/n的概率为结果

代码实现：

class Solution {
    //保存结果
    private int ans;
    private ListNode head;

    public Solution(ListNode head) {
        this.head=head;
    }
    public int getRandom() {
        //获得随机数
        Random random=new Random();
        ListNode cur=head;
        //历遍节点，计数
        for(int i=1;cur!=null;cur=cur.next,i++){
            if(random.nextInt(i)==0){
                ans=cur.val;
            }
        }
        return ans;
    }
}

水塘抽样算法进阶考虑：

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

• 为什么叫水塘抽样？因为结果集合像一个蓄水池，每次从未知大小的候选集（蓄水池源头水域）里面选取元素加入蓄水池，挤掉一部分——类似于蓄水池换水的过程

随机选取k个样本的实现过程

• 以0为序号起点保存前k个数为R（蓄水池）
• 从k+1个开始，即开始序列号为k，历遍S（候选集）
• 每次读取0~i（i为当前序列号）范围的随机数r，如果r in [0,k-1]，用S[i]替换R[r] (换水过程)

代码实现：

public int[] getRandom(int k) {
        //获得随机数
        Random random=new Random();
        ListNode cur=head;
    	int[] R=new int[k];
    
        //历遍节点
        for(int i=0;cur!=null;cur=cur.next,i++){
        	if(i<k){
                R[i]=cur.val;
            }
            else if(random.nextInt(i)<k){
                R[i]=cur.val;
            }
        }
        return R;
}

证明过程略（从后往前证明后n-k个数每个概率为k/n，初始k个数被换走概率相等）

结尾

题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems

??关注作者，带你刷题，从简单的算法题了解最常用的算法技能（寒假每日一题）
??关注作者刷题——简单到进阶，让你不知不觉成为无情的刷题机器