如何设计支持动态范围的UniqueRandomGenerator类，实现每次返回区间内唯一随机数

这里推荐两种高效的实现思路，可根据业务场景选择：

方案1：阈值切换采样（实现简单，适合绝大多数场景） #

通过动态切换采样策略，同时解决拒绝采样重试次数不稳定、数组预初始化前置成本高的问题，天然支持set_range操作。

类成员定义 #

#include <random>
#include <vector>
#include <unordered_set>
#include <algorithm>

class UniqueRandomGenerator {
private:
    int cur_start = 0, cur_end = 0;
    std::unordered_set<int> used; // 存储当前区间内已经返回过的数值
    std::vector<int> leftover; // 剩余可用数较少时预先生成的随机可用列表
    int pos = 0; // 遍历leftover的指针
    std::mt19937 rng{std::random_device{}()}; // 随机数生成器

public:
    int get();
    void set_range(int s, int e);
};

get() 实现逻辑 #

1. 计算当前区间总长度n = cur_end - cur_start + 1，剩余可用数cnt = n - used.size()
2. 如果cnt == 0，说明区间内所有数值都已经返回过，清空used和leftover，重置pos，进入下一轮循环
3. 当剩余可用数超过区间总长度的1/4时，使用拒绝采样：随机生成区间内的数值，不在used集合中就返回并加入used，此时重试期望次数不超过4次，性能稳定
4. 当剩余可用数不足1/4时，一次性生成所有可用数值并打乱，依次返回，后续get均为O(1)时间复杂度

int UniqueRandomGenerator::get() {
    int n = cur_end - cur_start + 1;
    int cnt = n - used.size();
    // 区间无剩余可用数，重置状态
    if (cnt == 0) {
        used.clear();
        leftover.clear();
        pos = 0;
        cnt = n;
    }
    // 剩余数较多，用拒绝采样
    if (cnt > n / 4) {
        std::uniform_int_distribution<int> dist(cur_start, cur_end);
        while (true) {
            int num = dist(rng);
            if (!used.count(num)) {
                used.insert(num);
                return num;
            }
        }
    }
    // 剩余数较少，预生成可用列表
    if (leftover.empty()) {
        for (int i = cur_start; i <= cur_end; i++) {
            if (!used.count(i)) {
                leftover.push_back(i);
            }
        }
        std::shuffle(leftover.begin(), leftover.end(), rng);
        pos = 0;
    }
    int res = leftover[pos++];
    used.insert(res);
    if (pos == leftover.size()) {
        leftover.clear();
    }
    return res;
}

set_range() 实现逻辑 #

1. 更新当前区间的上下限
2. 清理used集合，删除所有不在新区间内的数值（这些数值不再影响新区间的唯一性规则）
3. 清空之前预生成的leftover列表，重置遍历指针
4. 如果新区间内所有数值都已经返回过，清空used进入下一轮

void UniqueRandomGenerator::set_range(int s, int e) {
    cur_start = s;
    cur_end = e;
    // 清理不在新区间内的已返回数值
    for (auto it = used.begin(); it != used.end();) {
        if (*it < s || *it > e) {
            it = used.erase(it);
        } else {
            ++it;
        }
    }
    leftover.clear();
    pos = 0;
    // 新区间无可用剩余，直接重置
    int n = e - s + 1;
    if (used.size() >= n) {
        used.clear();
    }
}

方案优势 #

• 无前置O(n)成本，适合get调用次数少的场景
• 拒绝采样重试次数有明确上限，性能稳定
• set_range操作效率高，仅需清理不在新区间的已返回数值
• 完全符合题目给出的用例逻辑

方案2：延迟Fisher-Yates置换（适合超大区间场景） #

如果你的区间跨度非常大（比如1e6以上），可以用基于虚拟数组的延迟Fisher-Yates方案，完全避免遍历整个区间的操作，每次get均摊O(1)时间复杂度：

• 用哈希表存储虚拟数组的置换关系，不需要提前初始化整个区间的数组
• set_range时过滤置换表中落在新区间外的映射，更新剩余可用计数即可
• 实现复杂度稍高，但极致性能更适合超大区间的场景

内容的提问来源于stack exchange，提问作者user3903448