​LeetCode刷题实战382:链表随机节点


算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 链表随机节点,我们先来看题面:
https://leetcode-cn.com/problems/linked-list-random-node/


Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Implement the Solution class:
Solution(ListNode head) Initializes the object with the integer array nums.
int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.

给定一个单链表,随机选择链表的一个节点,并返回相应的节点值。保证每个节点被选的概率一样。
进阶:
如果链表十分大且长度未知,如何解决这个问题?你能否使用常数级空间复杂度实现?

示例

// 初始化一个单链表 [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();


解题

https://blog.csdn.net/Yubochang/article/details/109406986
最简单的就是统计个数,然后随机返回一个值回去,但是这样子就得两次遍历,第一次统计个数,第二次获得特定节点值,当然你也可以第一次遍历是把链表存在ArrayList里,然后直接get,但是这样太浪费内存。

另外的,就是采用蓄水池抽样算法,即第 i 个节点被抽取当作结果的概率为 1/i ,顺序概率抽取、替换,这样我们就不用去统计整体的n,也能保证被选中概率一样。

怎么保证?

数学归纳法:

第一个节点A,1/1的概率作为结果;

第二个节点B,1/2的概率作为结果,那么此时A就有1/2的概率被替换,于是A=1*1/2=1/2的概率不被替换,作为结果;

第三个节点C,1/3的概率作为结果,那么此时A=1/2*2/3=1/3,B=1/2*2/3=1/3概率不被替换,作为结果;

……

第n个节点,1/n的概率作为结果,那么此时A=1/(n-1)*(n-1)/n=1/n,B=…,C=…。

神奇吗?前面的节点的本身留下概率大,但是经过筛选的次数多导致概率下降,所以每一次筛选每个节点被选中概率都是一样的。


import java.util.Random;
class Solution {
 
    private ListNode ls;
 
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */

    public Solution(ListNode head) {
        ls=head;
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        ListNode tls=ls;
        Random rd=new Random(); //随机数随便,保证概率为1/i即可
        int i=1,rs=tls.val;
        while(tls!=null){
            if(rd.nextInt(i++)==0){
                rs=tls.val;
            }
            tls=tls.next;
        }
        return rs;
    }
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-380题汇总,希望对你有点帮助!
LeetCode刷题实战381:O(1) 时间插入、删除和获取随机元素 – 允许重复

​LeetCode刷题实战382:链表随机节点

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/14485.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息