【随机算法】黑名单映射

摘要: 黑名单映射在随机算法中的应用

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，最近我们密集地学习了常见的随机算法，并且解决了不少力扣中的问题。本文我们看两个力扣上的综合性较强的随机算法的问题，710 和 519。

这两道题的解法类似，都用到了黑名单映射的技巧，同时随机性体现在随机队列的使用上。

题目1

• 710. 黑名单中的随机数

给定一个包含 [0，n ) 中独特的整数的黑名单 B，写一个函数从 [ 0，n ) 中返回一个不在 B 中的随机整数。

对它进行优化使其尽量少调用系统方法 Math.random() 。

提示:

1 <= N <= 1000000000
0 <= B.length < min(100000, N)
[0, N) 不包含 N，详细参见 interval notation 。

算法: 随机队列 + 黑名单映射

假想一个随机队列，key 为 [0, N)，黑名单 B 长度为 nB，将这 nB 个数组映射到队尾的 nB 个元素 [N - nB, N - 1]。

实现方式为将黑名单元素与队尾节点交换，交换后，原位置视为持有了被交换的队尾节点的元素。

随机数只在 [0, N - nB) 范围取。若取到了一个被交换过的节点，查哈希表将其映射的队尾元素返回。

黑名单映射细节：将黑名单分为两类，大于等于 N - nB 的和小于 N - nB 的。

对于大于等于 N - nB 的这部分不做映射，它们本来就不会访问到。小于 N - nB 的，将其映射到大于等于 N - nB 且不在黑名单中的元素。

代码 (C++)

class Solution {
public:
    Solution(int N, vector<int>& blacklist) {
        int nB = blacklist.size();
        int n = N - nB;
        dre = std::default_random_engine();
        di = std::uniform_int_distribution<int>(0, n - 1);

        mapping = unordered_map<int, int>();
        unordered_set<int> B(blacklist.begin(), blacklist.end());
        for(int b: blacklist)
        {
            if(b >= n)
                continue;
            --N;
            while(B.count(N) > 0)
                --N;
            mapping[b] = N;
        }
    }

    int pick() {
        int r = di(dre);
        if(mapping.count(r) > 0)
            return mapping[r];
        else
            return r;
    }

private:
    unordered_map<int, int> mapping;
    std::default_random_engine dre;
    std::uniform_int_distribution<int> di;
};

---

题目2

• 519. 随机翻转矩阵

题中给出一个 n_rows 行 n_cols 列的二维矩阵，且所有值被初始化为 0。要求编写一个 flip 函数，均匀随机的将矩阵中的 0 变为 1，并返回该值的位置下标 [row_id,col_id]；同样编写一个 reset 函数，将所有的值都重新置为 0。尽量最少调用随机函数 Math.random()，并且优化时间和空间复杂度。

注意:

1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows 并且 0 <= col.id < n_cols
当矩阵中没有值为 0 时，不可以调用 flip 函数
调用 flip 和 reset 函数的次数加起来不会超过 1000 次

算法1: 哈希表维护黑名单+拒绝采样

如果每次选点都没有限制，则直接均匀采样横纵坐标即可。

由于在每次选点的时候，已经选过的点（已经置为1）不能被再次选中，因此相当于有一个黑名单，其中保存着不能被选中的点。

因此可以用哈希表维护一个黑名单，每次选点之后将选中的点加入黑名单，选点过程用拒绝采样即可。这是比较直接的做法，不过调用 Math.random() 会多一些。

代码 (C++)

class Solution {
public:
    Solution(int n_rows, int n_cols) {
        n = n_rows;
        m = n_cols;
        dre = std::default_random_engine();
        fliped = unordered_set<int>();
    }

    vector<int> flip() {
        std::uniform_int_distribution<int> di(0, n * m - 1);
        int random_idx = di(dre);
        while(fliped.count(random_idx) > 0)
            random_idx = di(dre);
        fliped.insert(random_idx);
        int x, y;
        idx2xy(random_idx, x, y);
        return {x, y};
    }

    void reset() {
        fliped.clear();
    }

private:
    int n, m;
    unordered_set<int> fliped;
    std::default_random_engine dre;

    void idx2xy(int idx, int& x, int& y)
    {
        x = idx / m;
        y = idx % m;
    }
};

算法2：随机队列 + 黑名单映射

用类似随机队列出队的处理方式：将选中的元素交换到末尾再弹出。

一开始队列中是 [0..m * n - 1] 的数据，数据量 len = m * n。产生 [0..m * n - 1] 的随机数的方式取出一个随机元素。将它交换到末尾 m * n - 1，数据量减一。

在第二轮队列中是 [0..len - 1] 的数据，产生 [0..len - 1] 的随机数的方式取出一个随机元素，交换到末尾 len - 1，数据量减一。

不用将队列显式建出来然后真正的交换，弹出，而是就维护一个数据量 len 作为随机数范围的依据。

还需要一个记录之前进行过的交换的数据结构。因为随机出的位置可能之前交换过了，那么需要一个哈希表记录该位置此时此刻持有的数据，也就是这个位置上一次弹出时候，是跟哪个位置的数据交换了。

代码 (C++)

class Solution {
public:
    Solution(int n_rows, int n_cols) {
        n = n_rows;
        m = n_cols;
        len = n_rows * n_cols;
        dre = std::default_random_engine();
        mapping = unordered_map<int, int>();
    }

    vector<int> flip() {
        std::uniform_int_distribution<int> di(0, len - 1);
        int random_idx = di(dre);
        int x, y;
        if(mapping.count(random_idx) == 0)
            idx2xy(random_idx, x, y);
        else
            idx2xy(mapping[random_idx], x, y);
        if(mapping.count(len - 1) == 0)
            mapping[random_idx] = len - 1;
        else
            mapping[random_idx] = mapping[len - 1];
        --len;
        return {x, y};
    }

    void reset() {
        len = n * m;
        mapping.clear();
    }

private:
    int n, m;
    int len;
    unordered_map<int, int> mapping;

    void idx2xy(int idx, int& x, int& y)
    {
        x = idx / m;
        y = idx % m;
    }
    std::default_random_engine dre;
};

---