C++二分算法：黑名单中的随机数

涉及知识点

二分查找

题目

给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
优化你的算法，使它最小化调用语言 内置 随机函数的次数。
实现 Solution 类:
Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数
示例 1：
输入
[“Solution”, “pick”, “pick”, “pick”, “pick”, “pick”, “pick”, “pick”]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]
解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
// 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4
参数范围
1 <= n <= 109
0 <= blacklist.length <= min(105, n - 1)
0 <= blacklist[i] < n
blacklist 中所有值都 不同
pick 最多被调用 2 * 104 次

错误解法 空间复杂度超出

分析

枚举[0,n)如果是黑名单种扔掉，否则放到m_vValue中。n 最大值10^9，必定超时。

代码

class Solution {
public:
Solution(int n, vector& blacklist) {
sort(blacklist.begin(), blacklist.end());
auto it = blacklist.begin();
for (int i = 0; i < n; i++)
{
while ((it != blacklist.end()) && (*it < i ))
{
++it;
}
if ((it != blacklist.end()) && (*it == i))
{
continue;
}
m_vValue.emplace_back(i);
}
srand(time(nullptr));
}
int pick() {
return m_vValue[rand() % m_vValue.size()];
}
vector m_vValue;
};

正确解法

分析

令黑名单的数量是m，那可以可以生成的数量是m_k=n-m。我们随机生成[0,m_k)的数字r，如果r在黑名单中则替换，否则直接返回r。

变量解释

注意

初始情况，iMay小于等于 *itBlackList ，如果两者相等则则itBalck++，所以iMay永远不会大于 *itBlackList

代码

class Solution {
public:
	Solution(int n, vector<int>& blacklist) {
		sort(blacklist.begin(), blacklist.end());
		const int m = blacklist.size();
		m_k = n - m;
		const auto it = std::lower_bound(blacklist.begin(), blacklist.end(), m_k);
		auto itNeedReplace = blacklist.begin();
		auto itBlackList = it;
		int iMay = m_k;
		for (; itNeedReplace != it ; ++itNeedReplace)
		{
			while ((itBlackList != blacklist.end()) && (iMay == *itBlackList ))
			{
				iMay++;
				++itBlackList;
			}
			m_mReplace[*itNeedReplace] = iMay++;
		}
		srand(time(nullptr));
	}
	int pick() {
		const int r = rand() % m_k;
		if (m_mReplace.count(r))
		{
			return m_mReplace[r];
		}
		return r;
	}
	std::unordered_map<int,int> m_mReplace;
	int m_k;
};
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

2023年3月版旧代码

struct SGroupInfo
{
SGroupInfo(int tBegin, int tLen, int tTotalLen)
{
begin = tBegin;
len = tLen;
totalLen = tTotalLen;
}
int End()const
{
return begin + len - 1;
}
int begin;
int len;
int totalLen;
};
class Solution {
public:
Solution(int N, vector& blacklist) {
m_iN = N;
m_iMaxRand = N - blacklist.size();
srand(time(nullptr));
std::sort(blacklist.begin(), blacklist.end());
if (blacklist.empty())
{
m_v.emplace_back(0, N, N);
return;
}
for (int i = 0; i < blacklist.size();i++)
{
const auto& n = blacklist[i];
if (0 == i )
{
const int len = n;
if (len > 0)
{
m_v.emplace_back(0, len, len);
}
}
else
{
const int len = n - blacklist[i-1] - 1;
if (len > 0)
{
const int iPreLen = m_v.empty() ? 0 : m_v.back().totalLen;
m_v.emplace_back(blacklist[i - 1] + 1, len, iPreLen + len);
}
}
}
const int len = m_iN - 1 - blacklist.back();
if (len > 0)
{
const int iPreLen = m_v.empty() ? 0 : m_v.back().totalLen;
m_v.emplace_back(blacklist.back() + 1, len, iPreLen + len);
}
}
int pick() {
const int index = rand() % m_iMaxRand;
auto it = std::lower_bound(m_v.begin(), m_v.end(), index+1, [](const SGroupInfo& group, const int& x2)
{return group.totalLen < x2; });
return it->begin + (index - (it->totalLen - it->len));
}
vector m_v;
int m_iN;
int m_iMaxRand;
};

2023年8月旧代码

class Solution {
public:
Solution(int n, vector& blacklist) {
m_iPickNum = n - blacklist.size();
std::set setHas(blacklist.begin(), blacklist.end());
int iReplace = m_iPickNum;
for (const auto& black : blacklist)
{
if (black >= m_iPickNum)
{
continue;
}
while (setHas.count(iReplace))
{
iReplace++;
}
m_mReplace[black] = iReplace++;
}
srand(time(nullptr));
}
int pick() {
int iRand = rand() % m_iPickNum;
if (m_mReplace.count(iRand))
{
return m_mReplace[iRand];
}
return iRand;
}
int m_iPickNum;
std::unordered_map m_mReplace;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院
，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17