【LetMeFly】710.黑名单中的随机数 - 预处理实现O(1)取值

力扣题目链接：https://leetcode.cn/problems/random-pick-with-blacklist/

给定一个整数 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 次

方法一：预处理实现O(1)取值

这一题我们可以预处理一下：把$[0,\min (n,10^5))$中未出现的数字记录下来。

具体方法为：
把blacklist排序，使用一个指针初始值指向下标0。
$i$从$[0,min(n,10^5))$遍历每一个数，如果指针已经达到了blacklist的结尾，就记录下当前遍历到的$i$，否则看$指针所指元素$和$i$是否相同：若相同就说明$i$在blacklist中，指针后移并且不记录$i$；否则记录下$i$
上述算法得益于“blacklist中的值互补相同”。如果blacklist中存在相同的值，那么在“$指针所指元素=i$”时，指针不断后移，直到$当前指针所指元素\ne i$

知道了$[0,\min (n,10^5))$中所有未出现过的数字，我们就能用$O(1)$的时间rand出一个值来。

具体方法为：
我们知道了$[0,\min (n,10^5))$中未出现的数字，就能求得$[0,n)$中所有未出现过的数字的个数：$allNum=[0,\min (n,10^5))中未出现的数字的个数+[10^5,n)的所有数字的个数$
这样只需要一次rand（$th=rand()\%allNum$就能在[0, allNum)范围内rand），拿$th$和$[0,n)$中所有未出现过的数字的个数做比较：小于则返回$[0,n)$中第$th+1$个未出现的值；否则返回从$1e5$开始的第$th-smallNum+1$个值

• 时间复杂度$O(N\log N+M)$，其中$N=min(n,10^5)$，$M$为调用次数。时间复杂度主要来自预处理，之后每次调用都只需要$O(1)$的时间复杂度。
• 空间复杂度$O(S\log S)$，其中$S=blacklist.length$。空间复杂度主要来自预处理的排序（$O(S\log S)$），只需要$O(S)$的额外空间存储未出现过的值。

AC代码

C++

class Solution {
private:
    vector<int> smallCan;  // 小范围数据可选取
    int n;
    int smallTo;
    int smallNum, allNum;
public:
    Solution(int n, vector<int>& blacklist): n(n) {
        sort(blacklist.begin(), blacklist.end());
        int loc = 0;
        int size = blacklist.size();
        smallTo = min(100000, n);
        for (int i = 0; i < smallTo; i++) {
            if (loc == size)
                smallCan.push_back(i);
            else {
                if (i == blacklist[loc]) {  // blacklist 中所有值都 不同
                    loc++;
                }
                else {
                    smallCan.push_back(i);
                }
            }
        }
        smallNum = smallCan.size();
        allNum = smallNum + (n - smallTo);
    }
    
    int pick() {
        int th = rand() % allNum;
        if (th < smallNum) {
            return smallCan[th];
        }
        else {
            return smallTo + (th - smallNum);
        }
    }
};
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

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125466455