LeetCode 382 Linked List Random Node

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

概述

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 的概率保持原有的选择。

证明：

不写了这个，没意义。

Links: leetcode-382-linked-list-random-node