链表随机节点
难度:
标签:
题目描述
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution 类：
Solution(ListNode head)使用整数数组初始化对象。int getRandom()从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
示例：
输入 ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []] 输出 [null, 1, 3, 2, 2, 3] 解释 Solution solution = new Solution([1, 2, 3]); solution.getRandom(); // 返回 1 solution.getRandom(); // 返回 3 solution.getRandom(); // 返回 2 solution.getRandom(); // 返回 2 solution.getRandom(); // 返回 3 // getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。
提示：
- 链表中的节点数在范围
[1, 104]内 -104 <= Node.val <= 104- 至多调用
getRandom方法104次
进阶：
- 如果链表非常大且长度未知，该怎么处理？
- 你能否在不使用额外空间的情况下解决此问题？
代码结果
运行时间: 184 ms, 内存: 17.3 MB
/*
* 思路：
* 1. 将链表转换为Stream流。
* 2. 使用Collectors.toList()方法将流转换为List。
* 3. 随机选择List中的一个元素。
*/
import java.util.*;
import java.util.stream.*;
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class Solution {
private List<Integer> nodeList;
private Random rand;
public Solution(ListNode head) {
this.nodeList = new ArrayList<>();
this.rand = new Random();
// 将链表转化为List
while (head != null) {
nodeList.add(head.val);
head = head.next;
}
}
public int getRandom() {
return nodeList.get(rand.nextInt(nodeList.size()));
}
}解释
方法:
该题解使用了一种称为「水塘抽样」的随机算法。基本思路是遍历链表，对于第 i 个节点，以 1/i 的概率选择该节点覆盖之前选中的节点。这样能保证选择每个节点的概率都是 1/n，其中 n 是链表的长度。在遍历过程中，用一个变量 node 来维护当前被选中的节点。遍历结束后，node 即为随机选择的节点。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在`水塘抽样`算法中，为什么选择每个节点的概率是以`1/i`进行决定，这是如何保证每个节点被选中概率相等的？
▷🦆
题解中提到，每次调用`getRandom()`方法时都需要从头遍历整个链表，这种设计是否存在性能优化的可能性，例如预处理或者使用额外的数据结构？
▷🦆
题解提到使用随机数`random.randint(0, i-1) == 0`来决定是否选择当前节点，这个条件具体是如何工作的，为什么随机数范围是`0`到`i-1`？
▷🦆
在链表结构变动（如节点添加或删除）的情况下，`Solution`类的设计需要做哪些调整才能继续正确地实现等概率随机选择？
▷相关问题
随机数索引
给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。
实现 Solution 类：
Solution(int[] nums)用数组nums初始化对象。int pick(int target)从nums中选出一个满足nums[i] == target的随机索引i。如果存在多个有效的索引，则每个索引的返回概率应当相等。
示例：
输入 ["Solution", "pick", "pick", "pick"] [[[1, 2, 3, 3, 3]], [3], [1], [3]] 输出 [null, 4, 0, 2] 解释 Solution solution = new Solution([1, 2, 3, 3, 3]); solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。 solution.pick(1); // 返回 0 。因为只有 nums[0] 等于 1 。 solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。
提示：
1 <= nums.length <= 2 * 104-231 <= nums[i] <= 231 - 1target是nums中的一个整数- 最多调用
pick函数104次