【蓄水池抽样】多语言入门「蓄水池抽样」知识点

宫水三叶的刷题日记

发布于 2022-05-27 14:07:52

3140

发布于 2022-05-27 14:07:52

文章被收录于专栏：宫水三叶的刷题日记

题目描述

这是 LeetCode 上的「382. 链表随机节点」，难度为「中等」。

Tag :「链表」、「模拟」、「蓄水池抽样」

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样。

实现 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中的一个，每个元素被返回的概率相等。

模拟

在查询时随机一个下标，并将数组中对应下标内容返回出去。

Java 代码：

class Solution {
    List<Integer> list = new ArrayList<>();
    Random random = new Random(20220116);
    public Solution(ListNode head) {
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
    }
    public int getRandom() {
        int idx = random.nextInt(list.size());
        return list.get(idx);
    }
}

Python（感谢 Benhao总提供的其他语言版本）：

class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.nodes = []
        while head:
            self.nodes.append(head)
            head = head.next

    def getRandom(self) -> int:
        return self.nodes[randint(0, len(self.nodes) - 1)].val

C++（感谢可乐总提供的其他语言版本）：

class Solution {
public:
    vector<int> list;
    Solution(ListNode* head) {
        while(head){
            list.push_back(head->val);
            head = head->next;
        }
    }
    int getRandom() {
        return list[rand() % list.size()];
    }
};

蓄水池抽样

Java 代码：

class Solution {
    ListNode head;
    Random random = new Random(20220116);
    public Solution(ListNode _head) {
        head = _head;
    }
    public int getRandom() {
        int ans = 0, idx = 0;
        ListNode t = head;
        while (t != null && ++idx >= 0) {
            if (random.nextInt(idx) == 0) ans = t.val;
            t = t.next;
        }
        return ans;
    }
}

Python（感谢 Benhao总提供的其他语言版本）：

class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.root = head

    def getRandom(self) -> int:
        node, ans, i = self.root, None, 0
        while node:
            if not randint(0, i):
                ans = node.val
            node, i = node.next, i + 1
        return ans

C++（感谢可乐总提供的其他语言版本）：

class Solution {
public:
    ListNode* head;
    Solution(ListNode* _head) {
        head = _head;
    }
    int getRandom() {
        int ans = 0, idx = 0;
        auto t = head;
        while(t != NULL){
            idx++;
            if(rand() % idx == 0) ans = t->val;
            t = t->next;
        }
        return ans;
    }
};