LeetCode382.链表随机节点：「随机访问」&「水塘抽样」

浏览次数 : 次 2022-01-16

博文字数统计 : 1.3k字 | 阅读所需时长 : 5分

× 文章目录

1. LeetCode382.链表随机节点：「随机访问」&「水塘抽样」

LeetCode382：链表随机节点
- 时间：2022-01-16
- 力扣难度：Medium
- 个人难度：Medium-
- 数据结构：链表
- 算法：水塘抽样、概率论与数理统计

LeetCode382.链表随机节点：「随机访问」&「水塘抽样」

1. 题目描述

题目：原题链接
- 给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点被选中的概率一样。
- 实现 Solution 类：
- Solution(ListNode head) 使用整数数组初始化对象。
- int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等
输入输出规范：设计题无需考虑输入输出

2. 方法一：两次遍历链表

思路：遍历两次链表
- 为了实现等概率的随机访问，最简单直观的思路就是对链表进行两次遍历
- 第一次遍历链表，得到其长度，然后在生成[0, n)之间的随机数作为索引
- 根据该随机索引，再次遍历链表，返回对应这个索引的链表元素

题解：直接遍历

class Solution {
    ListNode head;
    Random random;

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

    public int getRandom() {
        int len = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            len++;
        }
        int index = (int) random.nextInt(len);
        cur = head;
        while(index > 0) {
            index--;
            cur = cur.next;
        }
        return cur.val;
    }
}

复杂度分析：n 是链表的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

3. 方法二：利用集合的随机访问

思路：通过集合实现随机访问
- 对于方法一，需要遍历两次链表，复杂度较高，其原因在于链表的随机访问是$O(n)$的
- 那么，我们可以通过集合(数组、列表)这种$O(1)$级别随机访问的结构来提高运算效率
- 实际上，就是先遍历一次链表，将元素都放入List中，再生成随机数，获取对应元素即可，属于空间换时间的常规操作

题解

class Solution {
    ListNode head;
    Random random;

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

    public int getRandom() {
		List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while(cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        // nextInt(1)*(b-a+1)+a
        int index = (int) random.nextInt(list.size());
        return list.get(index);
    }
}

复杂度分析：n 是链表的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

4. 方法三：水塘抽样

思路：概率论：随机抽样
- 实际上，本题属于数据流中获取随机元素的问题，在数学上有一种专门用于解决该类问题的算法：水塘抽样算法，也称为蓄水池抽样算法
- 该算法的主要思想是
  - 维护一个初始值为0的变量 i，表示当前遍历到的元素的序号，遍历整个数据流(链表)，在遍历的过程中每次对维护的序号变量进行++操作
  - 然后生成一个[0, i)的随机数，当这个随机数等于0的时候，就选择当前遍历到的元素作为结果返回
  - 这样以来，我们就不需要知道整个元素的集合(无论是链表，还是抽象意义上的一个数据流)的大小，也不需要额外的空间去存放元素，非常适合在大数据场景下不知道数据具体个数时，随机返回指定个数(可以不为1)元素
- 简单证明
  - 对于 n 个元素，随机返回其中一个，只需要让每个元素被获取到的几率为 $1/n$ 即可
  - 那么，运用水塘抽样算法，我们可以发现，对于第 i 个元素，其随机值为0的概率$P(i) = \frac{1}{i}$，这只是表示该元素此时被选中的概率，最终如果确定选择该元素，则还需要后续元素不被选中(否则会被替换掉)
  - 此时，元素 i 被选中的概率为：$P_i = P(i)(1-P(i+1)…(1-P(n)) = \frac{1}{i}* \frac{i}{i+1}* \frac{i+1}{i+2}…* \frac{n-1}{n} = \frac{1}{n}$
  - 因此，每个元素被选中的概率都是$1/n$，实现随机抽样
- 扩展：对于抽样元素不为1时，假设抽样个数为 m
  - 同样地，需要每个元素被抽到的概率为 $m/n$
  - 首先，初始时保留前 m 个元素，且各个元素等概率，同样遍历所有元素，此时随机数取值为[0, m)时，表示本轮被选中
  - 遍历第 m+1 个元素时，随机数满足0 ~ m 的概率为：$\frac{m}{m+1}$
  - 而原来的 m 个元素中的某一个元素 k 存在的概率为：m+1被抽到×替换的元素是其他元素 + m+1没被抽到
  - 公式为：$P_k = \frac{m}{m+1}*\frac{m-1}{m} + \frac{1}{m+1} = \frac{m}{m+1}$
  - 递推到所有元素遍历完，该元素 k 还存在的概率：$m/n$

题解

class Solution {
       ListNode head;
       Random random;

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

       public int getRandom() {
        int i = 0;
           int res = 0;
           ListNode cur = head;
           while(cur != null) {
               i++;
               if(random.nextInt(i) == 0){
                   res = cur.val;
               }
               cur = cur.next;
           }
           return res;
       }
}

复杂度分析：n 是链表的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

本文作者： Chthollists
发布时间： 2022-01-16 20:15:33
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode382.链表随机节点：「随机访问」&「水塘抽样」
本文链接： https://chthollists.github.io/post/469ff2f.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！