每日一题(2022-01-16):链表随机节点

每日一题(2022-01-16):链表随机节点

来源:力扣
难度:中等
题目:382. 链表随机节点

题目详情

原题截图.png

题解思路

常规思路是空间换时间,可以用数组存储所有链表节点,然后直接对数组进行随机索引,空间复杂度O(n),时间复杂度O(1)
除此之外就是水塘抽样,这种抽样方式适合对样本数量巨大的集合进行随机抽样,空间复杂度可以达到O(1),与昨天的题目相似,这种算法思想的背后还是概率与统计的数学知识,下面贴一下官方题解对于这种抽样方式原理的解释:
官方题解.png
需要注意的问题是,OJ系统会在初始化Solution对象后多次调用getRandom函数进行随机节点的获取,这就需要我们确保不能在getRandom函数内对成员变量的值进行修改,自己的程序(下述注释的while版本代码)就是因为可以临时变量的数量而直接对头结点进行了迭代导致OJ出错;
压行害人啊!

代码结果

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    Solution(ListNode* head) {
        _m_pHead = head;
    }
    
    int getRandom() {

        int iIdx = 1, iResult = 0;
        
        // while (_m_pHead)
        // {
        //     if (!(rand() % iIdx++)) iResult = _m_pHead->val;
        //     _m_pHead = _m_pHead->next;
        // }

        for (ListNode* pTmpNode = _m_pHead; pTmpNode; pTmpNode = pTmpNode->next)
            if (!(rand() % iIdx++)) iResult = pTmpNode->val;

        return iResult;
    }

private:
    ListNode* _m_pHead;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(head);
 * int param_1 = obj->getRandom();
 */

运行结果.png