[leetcode]-Linked List Random Node
[leetcode]-Linked List Random Node
fengsehng 发表于1年前
[leetcode]-Linked List Random Node
  • 发表于 1年前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】如何购买服务器最划算?>>>   

题目描述:

给定一个单向的链表,要求以相等的概率返回

要求:

时间复杂度o(n),空间复杂度o(1)

原文描述:

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.

Follow up:

What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [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() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

思路分析:

  • 因为链表的长度不固定,也没法通过下标取值,只能一边遍利,一边取值
  • 考虑在遍历时候,动态记录长度n,然后保证当前值的返回概率是1/n,我们以第2个数为例(就是head.next.val)选取的概率为(1/2)* (2/3)(3/4) ……….. (n-1) / n = 1/n (选取第2个数在长度为2的时候为1/2,其他的都不要选)而对于任意的第x数,由于可以覆盖前面的数,均有: (1/x) * (x/(x+1)) *…….(n-1) / n = 1/n
  • 第n个数就直接1/n
  • -

代码:

import java.util.Random;

public class Solution {
     /** @param head The linked list's head. Note that the head is guaranteed to be not null, so it contains at least one node. */
    ListNode head = null;
    Random random = null;
    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }

    /** Returns a random node's value. */
    public int getRandom() {
        ListNode result = null;
        ListNode current = head;
        for(int n = 1;current != null;n++){
            if(random.nextInt(n) == 0){
                result = current;
            }
            current = current.next;
        }
        return result.val;
    }
}

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

这里写图片描述

共有 人打赏支持
粉丝 4
博文 284
码字总数 214494
×
fengsehng
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: