随机队列

  |  

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

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



$1 随机队列

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

push 的实现

直接插到 vector 的尾部。

pop 的实现

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

随机队列的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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

  • 测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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

分析

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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

代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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;
};

Share