LeetCode 710 Random Pick with Blacklist

标签: 数组类题目 LeetCode 发布于:2022-02-13 15:10:54 编辑于:2022-02-13 15:35:34 浏览量:376

概述

https://leetcode.com/problems/random-pick-with-blacklist/

暴力法

直接摇色子,命中黑名单后重摇色子。

但是题目中说了要尽量减少摇色子的次数。

隔离法

我们把黑名单中的值集中在数组的末尾,这样随机取样取之前的值就好。

具体的实现中,首先维护一个哈希表来快速查询一个值是否黑名单中,如果其在,则将其映射到一个 okay 的值。

第一次 WA 的原因:忘记在 i 赋给 m[b] 后递增 i,导致所有的坏索引映射到了同一个值。

class Solution {
public:
    unordered_map<int, int> m;
    int sz;
    Solution(int n, vector<int>& blacklist) {
        sz = n - blacklist.size();
        for (auto b : blacklist) m[b] = -1;  // mark as blocked
        int i = sz;
        for (auto b : blacklist) {
            if (b >= sz) continue;
            while (m.count(i)) { // while i is in blacklist
                i ++;
            }
            m[b] = i ++;
        }
    }
    
    int pick() {
        int i = rand() % sz;
        if (m.count(i)) {
            i = m[i];
        }
        return i;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/