leetcode Linked List Random Node

leetcode 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 list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

题目地址: leetcode Linked List Random Node

题意: 给定一个链表,要求以相等的概率返回链表上的结点。

思路:

若已知链表长度len,那么直接随机一下0~len-1,然后遍历到那个结点。

如果不知道长度呢?

我们实时的计算当前遍历了多少个元素cnt,然后以 1/cnt 的概率选择 当前的元素,直到遍历完链表。

这样遍历一遍即可。

为啥是对的?

我们以第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啦

大家都是1/n~

 

C++

Java

Python

注:在代码实现上,这里的cnt 比上面讲解中的cnt 少1   randint(x,y)返回的为[x,y]的闭区间。

 

 

本题是leetcode 382 Linked List Random Node 的题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Linked List Random Node
本文地址:https://www.hrwhisper.me/leetcode-linked-list-random-node/

您的支持将鼓励我继续创作!

Leetcode , , , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *