LeetCode382 链表随机节点

发表于 | 分类于 |
字数统计: 188 | 阅读时长 ≈ 1

链接： https://leetcode-cn.com/problems/linked-list-random-node/description/

题面

给定一个单向链表，要求设计一个算法，可以随机取得其中的一个数字

解法

这里要用到一个水库采样算法
水库算法：遍历这个链表，在遍历到第$i$个节点时，有 $1 / i$的概率选择这个节点覆盖掉之前的节点选择。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    /** @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;
    Solution(ListNode* head):Head(head) {

    }
    
    /** Returns a random node's value. */
    int getRandom() {
        int ans = Head -> val;
        ListNode* node = Head -> next;
        int index = 2;
        while(node != nullptr) {
            int flag = rand() % index == 0; 
            if (flag) {
                ans = node -> val;
            }
            index++;
            node = node -> next;
        }
        return ans;
        
    }
};