文档章节

[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
决战Leetcode: easy part(51-96)

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

qq_32690999
02/09
0
0
LeetCode:Odd Even Linked List - 链表内元素按奇偶位置重新排序

1、题目名称 Odd Even Linked List(链表内元素按奇偶位置重新排序) 2、题目地址 https://leetcode.com/problems/odd-even-linked-list/ 3、题目内容 英文: Given a singly linked list, ...

北风其凉
2016/01/22
2.1K
0

没有更多内容

加载失败,请刷新页面

加载更多

Mac OS X下Maven的安装与配置

Mac OS X 安装Maven: 下载 Maven, 并解压到某个目录。例如/Users/robbie/apache-maven-3.3.3 打开Terminal,输入以下命令,设置Maven classpath $ vi ~/.bash_profile 添加下列两行代码,之后...

TonyStarkSir
今天
3
0
关于编程,你的练习是不是有效的?

最近由于工作及Solution项目的影响,我在重新学习DDD和领域建模的一些知识。然后,我突然就想到了这个问题,以及我是怎么做的? 对于我来说,提升技能的项目会有四种: 纯兴趣驱动的项目。即...

问题终结者
今天
4
0
打开eclipse出现an error has occurred see the log file

解决方法: 1,打开eclipse安装目录下的eclipse.ini文件; 2,打开的文本文件最后添加一行 --add-modules=ALL-SYSTEM 3,保存重新打开Eclipse。...

任梁荣
昨天
4
0
搞定Northwind示例数据库,无论哪个版本的SQLServer都受用

Northwind数据库 从这里可以找到突破口: http://social.msdn.microsoft.com/Forums/zh-CN/Vsexpressvb/thread/8490a1c6-9018-40c9-aafb-df9f79d29cde 下面是MSDN: http://msdn2.microsoft......

QQZZFT
昨天
1
0
mysql主从同步,安装配置操作

准备 两台mysql服务,我这里准备了如下: 主库:192.168.176.128 从库:192.168.176.131 如何在Linux上安装mysql服务,请看https://blog.csdn.net/qq_18860653/article/details/80250499 操作...

小致dad
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部