0382. Linked List Random Node

题目信息

题号:

0382

难度:

Medium

主题:

单链表、随机节点、等概率、对象状态

原题:

LeetCode 0382

重点:

链表非空、每个节点而不是每个不同值等概率、重复值的概率会累加、每次调用返回一个节点值

题目重述

使用给定非空单链表的头节点构造对象,并实现 getRandom()。每次调用时,从链表的全部节点中等概率选择一个节点,返回该节点保存的整数值。

链表节点数位于 [1, 10^4],节点值位于 [-10^4, 10^4],getRandom 的调用次数不超过 10^4。等概率针对节点位置:若多个节点保存相同值,该值被返回的总概率等于这些节点概率之和。对象不应改变链表节点的次序或连接关系。

自建示例

重复值来自不同节点:

输入链表:4 -> 4 -> 9
调用:getRandom()
输出:4 或 9
解释:三个节点各有 1/3 概率被选中,因此返回值 4 的总概率为 2/3,返回 9 的概率为 1/3。

单节点链表:

输入链表:-6
调用:getRandom()
输出:-6
解释:链表只有一个节点,每次调用都必须返回它的值。

水塘抽样不预先知道链表长度

每次调用从头遍历链表,维护当前已经看到的节点数 count 和候选值。看到第 count 个节点时,以 1 / count 的概率用它替换候选。第一个节点必选;任意第 j 个节点最终被保留的概率是 1/j 乘以前面没有替换它的概率,恰好为 1/n。

这样无需先统计长度或复制节点,且不改变链表结构。

C++ 实现

class Solution {
    ListNode* head;
    std::mt19937 generator{std::random_device{}()};

public:
    Solution(ListNode* head) : head(head) {}

    int getRandom() {
        int count = 0;
        int chosen = 0;
        for (ListNode* node = head; node != nullptr;
             node = node->next) {
            ++count;
            std::uniform_int_distribution<int> distribution(1, count);
            if (distribution(generator) == 1) {
                chosen = node->val;
            }
        }
        return chosen;
    }
};

代码分析

水塘抽样保证每个节点位置等概率,而不是按节点值去重;重复值的概率会自动按对应节点数量相加。每次 getRandom 遍历 n 个节点,时间复杂度为 O(n),除随机状态外额外空间为 O(1)。