文档章节

[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
17
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
2018/10/23
0
0
决战Leetcode: easy part(51-96)

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

qq_32690999
2018/02/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

数据库表与表之间的一对一、一对多、多对多关系

表1 foreign key 表2 多对一:表 1 的多条记录对应表 2 的一条记录 利用foreign key的原理我们可以制作两张表的多对多,一对一关系 多对多: 表1的多条记录可以对应表2的一条记录 表2的多条记...

Garphy
40分钟前
6
0
MySQL 表崩溃修复

MySQL日志报错 2019-10-19 13:41:51 19916 [ERROR] /usr/local/mysql/bin/mysqld: Table './initread_hss/user_info' is marked as crashed and should be repaired2019-10-19 13:41:51 1......

雁南飞丶
50分钟前
6
0
Error和Exception

1.Error类和Exception类都是继承Throwable类 2.Error(错误)是系统中的错误,程序员是不能改变的和处理的,是在程序编译时出现的错误,只能通过修改程序才能修正。一般是指与虚拟机相关的问...

大瑞清_liurq
今天
4
0
8086汇编基础 start 程序入口标签的示例

    IDE : Masm for Windows 集成实验环境 2015     OS : Windows 10 x64 typesetting : Markdown    blog : my.oschina.net/zhichengjiu    gitee : gitee.com/zhichengjiu   ......

志成就
今天
4
0
uni app 零基础小白到项目实战2

<template> <scroll-view v-for="(card, index) in list" :key="index"> <view v-for =(item, itemIndex) in card"> {{item.value}}</view> </scroll-view></template> GraceUi va......

达达前端小酒馆
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部