IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【每日一题见微知著】水塘抽样算法——未知长度随机抽取问题 -> 正文阅读

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

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

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

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

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-01-17 11:44:21  更:2022-01-17 11:45:05 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 21:01:08-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码