涉及知识点
题目
给定一个整数 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。
变量解释
| it | 指向黑名点中首个大于等于m_k的数。[…,it)需要替换，替换的数必须大于等于m_k，且不能在[it,…)中，且不能相互重复。相互重复好解决：iMay自增，初始值等于m_k，这可以保证大于等于m_k。 |
| tNeedReplace | 指向需要替换的值 |
| itBlackList | 指向大于等于iMay的最小值。 |
注意
初始情况，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; };
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<int, int> 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
