LeetCode 382 Linked List Random Node

标签: 数学类题目 LeetCode 发布于:2022-03-01 11:03:52 编辑于:2022-03-01 11:12:46 浏览量:443

概述

https://leetcode.com/problems/linked-list-random-node/

暴力解

首先遍历一遍求得 n,然后取 1~n 之间的随机数,遍历过去找它即可。

初始化的时间复杂度 O(n),以后每次操作 O(n)。

class Solution {
public:
    int n = 0;
    ListNode* head;
    Solution(ListNode* head) {
        this->head = head;
        while (head) {
            head = head->next;
            n ++;
        }
    }
    
    int getRandom() {
        int t = rand() % n;
        auto c = head;
        while (t != 0) {
            c = c->next;
            t --;
        }
        return c->val;
    }
};

暴力法 + 缓存优化

一个简单的优化是拿数组存索引对应的节点:

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

数学法

https://labuladong.gitee.io/algo/4/30/123/

当你遇到第 i 个元素时,应该有 1/i 的概率选择该元素,1 - 1/i 的概率保持原有的选择。

证明:

不写了这个,没意义。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/