共计 711 个字符,预计需要花费 2 分钟才能阅读完成。
leetcode 382. 链表随机节点
给你一个单链表,随机抉择链表的一个节点,并返回相应的节点值。每个节点被选中的概率一样。
实现 Solution 类:
Solution(ListNode head) 应用整数数组初始化对象。
int getRandom() 从链表中随机抉择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。进阶:
如果链表十分大且长度未知,该怎么解决?
你是否在不应用额定空间的状况下解决此问题?
办法 1 [空间复杂度 O(n)]
咱们能够在初始化时,用一个数组记录链表中的所有元素,这样随机抉择链表的一个节点,就变成在数组中随机抉择一个元素。应用 rand()办法即可。
办法 2 [空间复杂度 O(1)]
应用蓄水池抽样算法:
假如有数据流 1, 2, 3, …, n。
怎么在不晓得 n 的具体值得状况下使得其中某个值 m 被抽样的概率为 1 / n 呢?
规定当遍历到 m 时咱们以 1 / m 的概率获得 m,那么最终后果为 m 的要求是:m+1, m+2, ... , n 都不会被抽到
,这些概率为 m /m+1,m+1/m+2, …, n-1/n。
综上,最终抽获得值为 m 的概率为 1 /m × m/m+1 × m+1/m+2 × … × n-1/n = 1/n。与 m 后面的值是否被抽样,因为 m 抽到会笼罩
。
长处:蓄水池抽样因为空间小,能够用于大数据流中的随机抽样问题。
代码
class Solution {
public:
ListNode* h;
Solution(ListNode* head) {h = head;}
int getRandom() {
int ans = 0, n = 1;
for (ListNode* p = h; p; p = p->next, n++) {if (rand() % n == 0) ans = p->val;
}
return ans;
}
};
正文完
发表至: leetcode算法
2022-02-15