LeetCode382-链表随机节点

2021-12-09

原题链接:【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相比。

图解如下:

clipboard

本题题解:

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

其余就都是链表的操作了。

代码实现如下:

//给定一个单链表,随机选择链表的一个节点,并返回相应的节点值。保证每个节点被选的概率一样。 
//
// 进阶: 
//如果链表十分大且长度未知,如何解决这个问题?你能否使用常数级空间复杂度实现? 
//
// 示例: 
//
// 
//// 初始化一个单链表 [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 水塘抽样 链表 数学 随机化 
//  172  0


//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)