文档章节

[leetcode]-Linked List Random Node

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 433
阅读 2
收藏 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面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
LeetCode目录。

按照LeetCode的Tags来区分的话,目前共有34个Tag,只列出已经解决的题,各分类中按照题目编号排序: Linked List。 Solved:21/28 Array。

Leafage_M
2017/11/21
0
0
[LeetCode] Shuffle an Array 数组洗牌

Shuffle a set of numbers without duplicates. Example: // Init an array with set 1, 2, and 3.int[] nums = {1,2,3};Solution solution = new Solution(nums);// Shuffle the array [1,2......

机器的心脏
2017/12/12
0
0
实现一个等可能返回任意节点的链表 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. Follow up: What if the linked lis......

叶枫啦啦
2017/12/29
0
0
【算法分析】如何理解快慢指针?判断linked list中是否有环、找到环的起始节点位置。以Leetcode 141. Linked List Cycle, 142. Linked List Cycle II 为例Python实现

引入 快慢指针经常用于链表(linked list)中环(Cycle)相关的问题。LeetCode中对应题目分别是: 141. Linked List Cycle 判断linked list中是否有环 142. Linked List Cycle II 找到环的起始节...

rgvb178
10/23
0
0
决战Leetcode: easy part(51-96)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
02/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

多线程的实现方式

多线程是指 一个程序运行时,产生或使用了不止一个线程。 线程的生命周期是怎么样的,下面这张图我们可以看出些端倪: 这章我们主要讨论多线程实现的方式,基础知识部分我们可以下来再恶补。...

搬砖大侠
6分钟前
0
0
新人千万不要在 Windows 上使用 Ruby on Rails

标题:新人千万不要在 Windows 上使用 Ruby on Rails 副标题:鼓励新人在 Linux 和 Mac 上使用 Ruby on Rails ! 原则:要走寻常路,不要学美特斯邦伟! "在 Windows上 使用 Ruby on Rails "是...

Jason909
14分钟前
0
0
day177-2018-12-14-英语流利阅读-待学习

艾滋病的治愈方法是否触手可及? Daniel 2018-12-14 1.今日导读 几十年来,艾滋病一直是世界上最难对付的“超级绝症”之一,从人类历史上第一次诊断出艾滋病病例的 20 世纪 80 年代早期到 20...

飞鱼说编程
40分钟前
7
0
java 合成两张图片或图片与二维码

java中偶尔会出现需要将一张小图片嵌入大图中或带二维码的海报图片,那么本文就是奔着这个目的来的,直接上腊肉! zxing是生成1D和2D条形或二维码的工具类库,java图形库Graphics2D进行图片的...

貔貅叔
45分钟前
4
0
80后阿里P10,“关老板”如何带着MaxCompute一路升级?

我是个幸运的人。虽然幸运不能被复制,但是眼光和努力可以。 关涛/关老板,80后的阿里P10,阿里巴巴通用计算平台负责人,阿里巴巴计算平台研究员。12年职场人生,微软和阿里的选择。 关涛的花...

阿里云官方博客
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部