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

简介: 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。

变量解释

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


相关文章
|
1天前
|
算法 JavaScript Java
【状态压缩】【动态规划】【C++算法】1125.最小的必要团队
【状态压缩】【动态规划】【C++算法】1125.最小的必要团队
|
1天前
|
算法 测试技术 C++
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
|
1天前
|
机器学习/深度学习 算法 测试技术
【动态规划】【C++算法】2742. 给墙壁刷油漆
【动态规划】【C++算法】2742. 给墙壁刷油漆
|
1天前
|
算法 测试技术 C++
【动态规划】【状态压缩】【C++算法】1815 得到新鲜甜甜圈的最多组数
【动态规划】【状态压缩】【C++算法】1815 得到新鲜甜甜圈的最多组数
|
1天前
|
机器学习/深度学习 算法 测试技术
【动态规划】【C++算法】1563 石子游戏 V
【动态规划】【C++算法】1563 石子游戏 V
|
1天前
|
算法 测试技术 C++
【记忆化搜索】【剪枝】【C++算法】1553吃掉 N 个橘子的最少天数
【记忆化搜索】【剪枝】【C++算法】1553吃掉 N 个橘子的最少天数
|
1天前
|
算法 测试技术 C++
【双指针】【C++算法】1537. 最大得分
【双指针】【C++算法】1537. 最大得分
|
1天前
|
算法 测试技术 C++
【动态规划】【中位数】【C++算法】1478. 安排邮筒
【动态规划】【中位数】【C++算法】1478. 安排邮筒
|
1天前
|
算法 测试技术 C++
【动态规划】【数学】【C++算法】1449. 数位成本和为目标值的最大数字
【动态规划】【数学】【C++算法】1449. 数位成本和为目标值的最大数字
|
1天前
|
人工智能 移动开发 算法
【动态规划】【C++算法】LeetCoce996正方形数组的数目
【动态规划】【C++算法】LeetCoce996正方形数组的数目