随机队列

摘要: 本文介绍随机队列的原理和代码模板，以及 2 道 leetcode 相关题目。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

• 随机队列
• 增加删 key 的支持
  • 380. 常数时间插入、删除和获取随机元素
  • 381. O(1) 时间插入、删除和获取随机元素 - 允许重复

---

$1 随机队列

与普通队列相比，除了pop随机元素而非队头元素之外，没有其它变化。

push 的实现

直接插到 vector 的尾部。

pop 的实现

选出随机下标后，将对应元素与 vector 的尾部元素交换，然后将将尾部弹出

随机队列的实现

#include <random>
#include <vector>
#include <iostream>

using namespace std;

class RandomQueue
{
public:
    RandomQueue()
    {
        data = vector<int>();
        dre = std::default_random_engine();
        dr = std::uniform_real_distribution<double>(0.0, 1.0);
    }

    bool empty()
    {
        return data.empty();
    }

    void push(int val)
    {
        data.push_back(val);
    }

    int pop()
    {
        if(data.empty())
            return -1;
        int n = data.size();
        int random_idx = floor(n * dr(dre));
        swap(data[n - 1], data[random_idx]);
        int val = data.back();
        data.pop_back();
        return val;
    }

private:
    vector<int> data;
    std::default_random_engine dre;
    std::uniform_real_distribution<double> dr;
};

测试：二叉树层序遍历，每层节点随机数出

• 用例: 四层满二叉树，节点值 0 ~ 14

0
1 2
3 4 5 6
7 8 9 10 11 12 13 14

• 测试代码

int main()
{
    int n = 15;
    vector<int> tree(n);
    for(int i = 0; i < n; ++i)
        tree[i] = i;
    RandomQueue rq;
    rq.push(0);
    vector<int> level_nodes;
    int level = 0;
    while(!rq.empty())
    {
        level_nodes.clear();
        while(!rq.empty())
            level_nodes.push_back(rq.pop());
        cout << "level " << level++ << ": ";
        for(int node: level_nodes)
        {
            cout << tree[node] << " ";
            if(node * 2 + 1 < n)
                rq.push(tree[node * 2 + 1]);
            if(node * 2 + 2 < n)
                rq.push(tree[node * 2 + 2]);
        }
        cout << endl;
    }
}

• 测试结果

$2 增加删 key 的支持

无重复 key

• 380. 常数时间插入、删除和获取随机元素

分析

在随机队列基础上增加按 key 删除。用哈希表对数组做索引。删除时仍然是将对应元素交换到 vector 尾部删除。

代码

class RandomizedSet {
public:
    RandomizedSet() {
        data = vector<int>();
        mapping = unordered_map<int, int>();
        dre = std::default_random_engine();
        dr = std::uniform_real_distribution<double>(0.0, 1.0);
    }

    bool insert(int val) {
        if(mapping.count(val) != 0)
            return false;
        int n = data.size();
        mapping[val] = n;
        data.push_back(val);
        return true;
    }

    bool remove(int val) {
        if(mapping.count(val) == 0)
            return false;
        int idx = mapping[val];
        int n = data.size();
        int tail = data[n - 1];
        swap(data[idx], data[n - 1]);
        data.pop_back();
        mapping[tail] = idx;
        mapping.erase(val);
        return true;
    }

    int getRandom() {
        if(data.empty())
            return -1;
        int n = data.size();
        // [0..1) -> [0 .. n-1]
        // 0 <= r * n < n
        int random_idx = floor(n * dr(dre));
        return data[random_idx];
    }

private:
    vector<int> data; // idx -> key
    unordered_map<int, int> mapping; // key -> idx
    std::default_random_engine dre;
    std::uniform_real_distribution<double> dr;
};

可以有重复 key

• 381. O(1) 时间插入、删除和获取随机元素 - 允许重复

代码

将维护哈希映射的数据结构改为可以支持重复键的哈希表。

class RandomizedCollection {
public:
    RandomizedCollection() {
        data = vector<int>();
        mapping = unordered_map<int, unordered_set<int>>();
        int rand_seed = rand();
        dre = std::default_random_engine(rand_seed);
        dr = std::uniform_real_distribution<double>(0.0, 1.0);
    }

    bool insert(int val) {
        bool has_val = mapping.count(val) == 0;
        int n = data.size();
        mapping[val].insert(n);
        data.push_back(val);
        return has_val;
    }

    bool remove(int val) {
        if(mapping.count(val) == 0)
            return false;
        int idx = *(mapping[val].begin());
        int n = data.size();
        int tail = data[n - 1];
        swap(data[n - 1], data[idx]);
        data.pop_back();
        mapping[val].erase(mapping[val].find(idx));
        if(n - 1 != idx)
        {
            mapping[tail].erase(n - 1);
            mapping[tail].insert(idx);
        }
        if(mapping[val].empty())
            mapping.erase(val);
        return true;
    }

    int getRandom() {
        if(data.empty())
            return -1;
        int n = data.size();
        int random_idx = floor(n * dr(dre));
        return data[random_idx];
    }

private:
    vector<int> data;
    unordered_map<int, unordered_set<int>> mapping;
    std::default_random_engine dre;
    std::uniform_real_distribution<double> dr;
};

---