Hard

题目描述

给定一个整数 n 和一个由不重复整数组成的黑名单数组 blacklist。设计一个算法，从范围 [0, n - 1] 中随机选取一个不在黑名单中的整数。范围内任何不在黑名单中的整数都应该有相等的返回概率。

优化你的算法，使其最小化对语言内置随机函数的调用次数。

实现 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 <= 10^9
  • 0 <= blacklist.length <= min(10^5, n - 1)
  • 0 <= blacklist[i] < n
  • blacklist 的所有值都是唯一的
  • 最多调用 pick 2 * 10^4 次

解题思路

这道题的核心挑战是如何在大范围内高效地随机选择不在黑名单中的数字。

方法分析：

  1. 直接法：每次随机生成数字，如果在黑名单中就重新生成。但当黑名单很大时效率低。

  2. 映射压缩法（推荐）：将问题转化为在连续区间内随机选择。核心思想是将范围 [0, n-1] 分为两部分：[0, n-blacklist.length-1] 和 [n-blacklist.length, n-1]。如果前半部分的数字在黑名单中，就将其映射到后半部分不在黑名单中的数字。

具体实现：

  • 统计有效数字个数：validCount = n - blacklist.length
  • 对于黑名单中小于 validCount 的数字，将其映射到 [validCount, n-1] 范围内不在黑名单中的数字
  • 每次 pick() 时，在 [0, validCount-1] 范围内随机生成数字，如果该数字有映射则返回映射值，否则返回原值

这样确保了每次只需要一次随机数生成，时间复杂度为 O(1)。

代码实现

class Solution {
private:
    int validCount;
    unordered_map<int, int> mapping;
    
public:
    Solution(int n, vector<int>& blacklist) {
        validCount = n - blacklist.size();
        
        unordered_set<int> blackSet(blacklist.begin(), blacklist.end());
        
        int mapTo = validCount;
        for (int b : blacklist) {
            if (b < validCount) {
                while (blackSet.count(mapTo)) {
                    mapTo++;
                }
                mapping[b] = mapTo++;
            }
        }
    }
    
    int pick() {
        int randIdx = rand() % validCount;
        return mapping.count(randIdx) ? mapping[randIdx] : randIdx;
    }
};

class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        self.valid_count = n - len(blacklist)
        self.mapping = {}
        
        black_set = set(blacklist)
        
        map_to = self.valid_count
        for b in blacklist:
            if b < self.valid_count:
                while map_to in black_set:
                    map_to += 1
                self.mapping[b] = map_to
                map_to += 1

    def pick(self) -> int:
        import random
        rand_idx = random.randint(0, self.valid_count - 1)
        return self.mapping.get(rand_idx, rand_idx)

public class Solution {
    private int validCount;
    private Dictionary<int, int> mapping;
    private Random random;
    
    public Solution(int n, int[] blacklist) {
        validCount = n - blacklist.Length;
        mapping = new Dictionary<int, int>();
        random = new Random();
        
        HashSet<int> blackSet = new HashSet<int>(blacklist);
        
        int mapTo = validCount;
        foreach (int b in blacklist) {
            if (b < validCount) {
                while (blackSet.Contains(mapTo)) {
                    mapTo++;
                }
                mapping[b] = mapTo++;
            }
        }
    }
    
    public int Pick() {
        int randIdx = random.Next(validCount);
        return mapping.ContainsKey(randIdx) ? mapping[randIdx] : randIdx;
    }
}

var Solution = function(n, blacklist) {
    this.validCount = n - blacklist.length;
    this.mapping = new Map();
    
    const blackSet = new Set(blacklist);
    
    let mapTo = this.validCount;
    for (const b of blacklist) {
        if (b < this.validCount) {
            while (blackSet.has(mapTo)) {
                mapTo++;
            }
            this.mapping.set(b, mapTo++);
        }
    }
};

Solution.prototype.pick = function() {
    const randIdx = Math.floor(Math.random() * this.validCount);
    return this.mapping.has(randIdx) ? this.mapping.get(randIdx) : randIdx;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(B)O(B)
pick()O(1)O(1)

其中 B 是黑名单的长度。初始化时需要遍历黑名单建立映射关系，pick 操作只需要一次随机数生成和哈希表查询，效率很高。

相关题目