LeetCode382-链表随机节点 LeetCode382-链表随机节点

原题链接：【382. 链表随机节点】：https://leetcode-cn.com/problems/linked-list-random-node/
题目描述：给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
示例:

// 初始化一个单链表 [1,2,3]. ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); Solution solution = new Solution(head); // getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。 solution.getRandom();

相关知识点：水塘抽样链表数学随机化
解题思路：一般的想法就是，我先遍历一遍链表，得到链表的总长度 n，再生成一个 [1,n] 之间的随机数为索引，然后再遍历链表，找到索引对应的节点，不就是一个随机的节点了吗？
但是由题目可知，链表十分大，且长度未知，也就说，我们不知道链表长度n，也就没办法取中间的随机数，那么我们应该怎么去取值呢？

由于是链表，所以我们可以一个节点一个节点遍历加载进入内存。虽然我们无法知道链表总长度，但是我们可以知道我们当前遍历的节点的长度i。
比如我们已经遍历了i个元素，可以从这i个元素中随机取了一个元素a，那如果现在再给你一个新元素b，你是继续留着a呢？还是抽取b作为样本结果呢？以什么样的原则来选择a和b呢？你的选择能够保证概率相等吗？

这里就用到了著名的蓄水池抽样算法。
蓄水池抽样算法假设给定一个数据流，数据流长度N很大，如何从中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。

当k = 1，只取一个元素时，要保证每条数据被抽取到的概率相等，那么每个数被抽取的概率应该为1/N，只要采取这种策略，只需要遍历一遍数据流就可以得到采样值，并且保证所有数据被选中的概率均为1/N 当k > 1，取k个元素时，要保证每条数据被抽取到的概率相等，那么每个数被抽取的概率应该为k / N。

算法实现思路为：

一个一个遍历数据流，在取第i个数据的时候，生成一个0到1的随机数p，如果p < k / i，替换池中任意一个数替换为第i个数；当p > k / i，继续保留前面的数。直到数据流结束，返回此k个数。但是为了保证计算准确性，一般是生成一个0到i的随机数，跟k相比。

图解如下：

文章图片

本题题解：注意这里其实就是K=1的情况，取随机数rand，范围为【0，i)，随机数+1，变成【1，i】范围，两边都是闭合的，更容易理解。所以，原来的小于k，即小于1，现在+1，四舍五入都变成了1，所以边界判断范围就是，随机数rand=1，则样本替换为当前遍历的节点，否则保留之前的样本节点，继续往下遍历。
其余就都是链表的操作了。
【LeetCode382-链表随机节点】代码实现如下：

//给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。 // // 进阶: //如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？ // // 示例: // // //// 初始化一个单链表 [1,2,3]. //ListNode head = new ListNode(1); //head.next = new ListNode(2); //head.next.next = new ListNode(3); //Solution solution = new Solution(head); // //// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。 //solution.getRandom(); // // Related Topics 水塘抽样链表数学随机化 //1720//leetcode submit region begin(Prohibit modification and deletion)import java.util.Random; /** * 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 {// 需要将链表传递给getRandom方法，所以只能提取作为类变量 ListNode head; public Solution(ListNode head) { this.head = head; }public int getRandom() { // 定义一个变量，存储采样的结果值 int result = 0; // 定义一个变量i，标记遍历到了第几个节点 int i = 0; // 将当前链表head指针赋值给cur ListNode cur = head; // 循环遍历链表 while (cur != null) { i++; // 取随机数rand 范围 [1, i] int rand = new Random().nextInt(i) + 1; // 因为rand最小值为1，这个边界只能取rand = 1 if (rand == 1) { result = cur.val; } // 指针往后移动，遍历下一个节点 cur = cur.next; }// 返回采样结果 return result; } }/** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */ //leetcode submit region end(Prohibit modification and deletion)