【leetcode】 382 Linked List Random Node

发表于 | 分类于 ，

随机返回一个链表中的值


描述

随机返回一个链表中的值

样例

1
2
输入: [1,2,3]
输出: 1,2,3等概率输出

思路

将链表存储到一个数组中，发现将数组保存为成员变量，构造函数初始化比保存头节点成员变量快，因为 getRandom() 是要多次调用的。

代码

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
27
28
29
//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
private:
    vector<int> res;

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. */
    Solution(ListNode* head) {
        ListNode *p = head;
        while (p) {
            res.push_back(p->val);
            p = p->next;
        }
    }

    /** Returns a random node's value. */
    int getRandom() {
        static default_random_engine e(time(0));
        std::uniform_int_distribution<int> u(0, res.size() - 1);
        return res[u(e)];
    }
};

参考

原题链接