LeetCode382. 链表随机节点🌟🌟🌟中等
课后作业
问题描述
原文链接：382. 链表随机节点
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点被选中的概率一样 。
实现 Solution 类：
Solution(ListNode head)使用整数数组初始化对象。int getRandom()从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
示例：
输入
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]
解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。
提示：
- 链表中的节点数在范围
[1, 104]内 -104 <= Node.val <= 104- 至多调用
getRandom方法104次
代码实现
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
ListNode head = null;
Random random = null;
public Solution(ListNode head) {
this.head = head;
this.random = new Random();
}
public int getRandom2() {
//方法1 统计长度 O(n)= 2n. O(1)
int n = 1;
ListNode cur = head;
while(cur.next != null){
n++;
cur = cur.next;
}
int k = random.nextInt(n) + 1;
cur = head;
for(int i = 1; i < k;i++){
cur = cur.next;
}
return cur.val;
}
public int getRandom() {
//方法2
ListNode cur = head;
int i = 1;
int res = cur.val;
while(cur != null){
if(random.nextInt(i) == 0){
res = cur.val;
}
cur = cur.next;
i++;
}
return res;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import random
class Solution(object):
def __init__(self, head):
"""
:type head: Optional[ListNode]
"""
self.head = head
self.random = random
def getRandom2(self):
# 方法1 统计长度 O(n) = 2n. O(1)
n = 1
cur = self.head
while cur.next:
n += 1
cur = cur.next
k = self.random.randint(1, n)
cur = self.head
for i in range(1, k):
cur = cur.next
return cur.val
def getRandom(self):
# 方法2
cur = self.head
i = 1
res = cur.val
while cur:
if self.random.randint(1, i) == 1:
res = cur.val
cur = cur.next
i += 1
return res
# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
Solution(ListNode* head) {
this->head = head;
std::srand(std::time(nullptr)); // 初始化随机数种子
}
int getRandom2() {
// 方法1 统计长度 O(n)= 2n. O(1)
int n = 1;
ListNode* cur = head;
while(cur->next != nullptr){
n++;
cur = cur->next;
}
int k = std::rand() % n + 1;
cur = head;
for(int i = 1; i < k; i++){
cur = cur->next;
}
return cur->val;
}
int getRandom() {
// 方法2
ListNode* cur = head;
int i = 1;
int res = cur->val;
while(cur != nullptr){
if(std::rand() % i == 0){
res = cur->val;
}
cur = cur->next;
i++;
}
return res;
}
private:
ListNode* head;
};
Go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
type Solution struct {
head *ListNode
}
func Constructor(head *ListNode) Solution {
return Solution{head: head}
}
func (this *Solution) GetRandom2() int {
// 方法1 统计长度 O(n)= 2n. O(1)
n := 1
cur := this.head
for cur.Next != nil {
n++
cur = cur.Next
}
k := rand.Intn(n) + 1
cur = this.head
for i := 1; i < k; i++ {
cur = cur.Next
}
return cur.Val
}
func (this *Solution) GetRandom() int {
// 方法2
cur := this.head
i := 1
res := cur.Val
for cur != nil {
if rand.Intn(i) == 0 {
res = cur.Val
}
cur = cur.Next
i++
}
return res
}
评论(6)
计算链表的长度n，利用随机函数取一个k值，求出k节点的val
打卡
//每次以1/i的概率选择第i个节点
class Solution {
private:
ListNodehead;//定义头结点并初始化
public:
Solution(ListNode_head) :head(_head){}
};
看到题目结果返回的是数组，就想用数组求解，可是时空复杂度均不理想。
方法一：统计链表长度，生成n个随机数，再遍历链表返回
方法二：
蓄水池抽样算法：当你遇到第
i个元素时，应该有1/i的概率选择该元素，1 - 1/i的概率保持原有的选择。打卡