LeetCode 710 Random Pick with Blacklist

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

概述

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;
    }
};

Links: leetcode-710-random-pick-with-blacklist