Involving knowledge points
binary search
Title
Given an integer n and a non-duplicate blacklist integer array blacklist . Design an algorithm to select an integer that is not included in the blacklist from any integer in the range [0, n – 1]. Any integer in the above range that is not in the blacklist should have an equal chance of being returned.
Optimize your algorithm so that it minimizes the number of calls to the language’s built-in random functions.
Implement the Solution class:
Solution(int n, int[] blacklist) initializes the integer n and the integer added to the blacklist blacklist
int pick() returns a random integer in the range [0, n – 1] that is not in the blacklist blacklist
Example 1:
enter
[“Solution”, “pick”, “pick”, “pick”, “pick”, “pick”, “pick”, “pick”]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
output
[null, 0, 4, 1, 6, 1, 0, 4]
explain
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // Return 0, any integer [0,1,4,6] is acceptable. Note that for each call to pick,
// The return probabilities of 0, 1, 4 and 6 must be equal (that is, the probability is 1/4).
solution.pick(); // return 4
solution.pick(); // return 1
solution.pick(); // return 6
solution.pick(); // return 1
solution.pick(); // return 0
solution.pick(); // return 4
Parameter range
1 <= n <= 109
0 <= blacklist.length <= min(105, n - 1)
0 <= blacklist[i] < n
All values in blacklist are different
pick is called at most 2 * 104 times
Wrong solution space complexity exceeded
Analysis
If the enumeration [0,n) is a blacklist, throw it away, otherwise put it in m_vValue. The maximum value of n is 10^9, which must time out.
Code
class Solution {
public:
Solution(int n, vector & amp; blacklist) {
sort(blacklist.begin(), blacklist.end());
auto it = blacklist.begin();
for (int i = 0; i < n; i + + )
{
while ((it != blacklist.end()) & amp; & amp; (*it < i ))
{
+ + it;
}
if ((it != blacklist.end()) & amp; & amp; (*it == i))
{
continue;
}
m_vValue.emplace_back(i);
}
srand(time(nullptr));
}
int pick() {
return m_vValue[rand() % m_vValue.size()];
}
vector m_vValue;
};
Correct solution
Analysis
Let the number of blacklists be m, then the number that can be generated is m_k=n-m. We randomly generate a number r in [0,m_k), and replace it if r is in the blacklist, otherwise return r directly.
Variable explanation
| it | points to black The first number in the name point that is greater than or equal to m_k. […,it) needs to be replaced. The replacement number must be greater than or equal to m_k, and cannot be in [it,…), and cannot repeat each other. It is easy to solve by repeating each other: iMay increases automatically, and the initial value is equal to m_k, which can ensure that it is greater than or equal to m_k. |
| tNeedReplace | points to the value that needs to be replaced |
| itBlackList | points to Greater than or equal to the minimum value of iMay. |
Note
In the initial case, iMay is less than or equal to *itBlackList. If the two are equal, then itBalck + +, so iMay will never be greater than *itBlackList.
Code
class Solution {<!-- -->
public:
Solution(int n, vector<int> & amp; 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()) & amp; & amp; (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;
};
March 2023 version of the old code
structSGroupInfo
{
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 & amp; 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 & amp; group, const int & amp; x2)
{return group.totalLen < x2; });
return it->begin + (index – (it->totalLen – it->len));
}
vector m_v;
int m_iN;
int m_iMaxRand;
};
Old code in August 2023
class Solution {
public:
Solution(int n, vector & amp; blacklist) {
m_iPickNum = n – blacklist.size();
std::set setHas(blacklist.begin(), blacklist.end());
int iReplace = m_iPickNum;
for (const auto & amp; 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
};
Extended reading
Video course
Effective learning: clear goals, timely feedback, stretching area (appropriate difficulty), you can learn simple courses first, please move to CSDN Academy
, listen to the explanation of Lecturer Baiyin (that is, I).
https://edu.csdn.net/course/detail/38771
If you want to quickly form a battle and share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses
https://edu.csdn.net/lecturer/6176
Related downloads
If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653
| What I want to say to you |
|---|
| It is a good wish to be happy when you hear the flaws. Discover problems and correct them early to save your boss money. |
| The origin of the Mohist name: everything is recorded in Mohism. |
| If the program is a one-stop process, then the algorithm is its key point |
Test environment
Operating system: win7 Development environment: VS2019 C++ 17
Or Operating system: win10 Development environment: VS2022 C++ 17
