0382. Linked List Random Node ============================= 题目信息 -------- :题号: 0382 :难度: Medium :主题: 单链表、随机节点、等概率、对象状态 :原题: `LeetCode 0382 `_ :重点: 链表非空、每个节点而不是每个不同值等概率、重复值的概率会累加、每次调用返回一个节点值 题目重述 -------- 使用给定非空单链表的头节点构造对象,并实现 ``getRandom()``。每次调用时,从链表的全部节点中等概率选择一个节点,返回该节点保存的整数值。 链表节点数位于 ``[1, 10^4]``,节点值位于 ``[-10^4, 10^4]``,``getRandom`` 的调用次数不超过 ``10^4``。等概率针对节点位置:若多个节点保存相同值,该值被返回的总概率等于这些节点概率之和。对象不应改变链表节点的次序或连接关系。 自建示例 -------- 重复值来自不同节点: .. code-block:: text 输入链表:4 -> 4 -> 9 调用:getRandom() 输出:4 或 9 解释:三个节点各有 1/3 概率被选中,因此返回值 4 的总概率为 2/3,返回 9 的概率为 1/3。 单节点链表: .. code-block:: text 输入链表:-6 调用:getRandom() 输出:-6 解释:链表只有一个节点,每次调用都必须返回它的值。 水塘抽样不预先知道链表长度 ---------------------------- 每次调用从头遍历链表,维护当前已经看到的节点数 ``count`` 和候选值。看到第 ``count`` 个节点时,以 ``1 / count`` 的概率用它替换候选。第一个节点必选;任意第 ``j`` 个节点最终被保留的概率是 ``1/j`` 乘以前面没有替换它的概率,恰好为 ``1/n``。 这样无需先统计长度或复制节点,且不改变链表结构。 C++ 实现 -------- .. code-block:: cpp 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 distribution(1, count); if (distribution(generator) == 1) { chosen = node->val; } } return chosen; } }; 代码分析 -------- 水塘抽样保证每个节点位置等概率,而不是按节点值去重;重复值的概率会自动按对应节点数量相加。每次 ``getRandom`` 遍历 ``n`` 个节点,时间复杂度为 ``O(n)``,除随机状态外额外空间为 ``O(1)``。