Simple O(1) pick 97.7% time 86.34% space with explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need a random number that is not in the blacklist.  This may seem difficult, but onc
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need a random number that is not in the blacklist.  This may seem difficult, but once you realize that we need a number that is **between** the numbers in that blacklist, it becomes simple\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nWe keep a list of intervals.\n\nIf the blacklist is empty, then we simply add the interval [ 0,n ) to our intervals;\n\nOtherwise, we sort the numbers in the blacklist.  We add intervals [0, min_blacklist) ans [max_blacklist+1, n) to our list, but only if those intervals are non-empty.  We then the intervals between blacklist numbers to our list, only if they are non-empty.\n\nIn pick(), we pick a random interval, and then a random number in that interval.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nlog(n)) for constructor, O(1) for pick.\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n) for constructor, O(1) for pick.\n\n# Code\n```\nclass Solution {\n    vector<pair<int, int>> intervals;\npublic:\n    Solution(int n, vector<int>& blacklist) {\n        if(!blacklist.size()) {\n            intervals.push_back({0, n});\n        } else {\n            sort(blacklist.begin(), blacklist.end());\n\n            //Add intervals outside the bounds of the blacklist\n            int mn = blacklist.front();\n            int mx = blacklist.back();\n            if(mn > 0) {\n                intervals.push_back({0, mn});\n            }\n\n            if(mx < n-1) {\n                intervals.push_back({mx+1, n});\n            }\n\n            //Add intervals between bounds of the blacklist\n            for(size_t i = 1; i < blacklist.size(); ++i) {\n                if(blacklist[i] - blacklist[i-1] > 1) {\n                    intervals.push_back({blacklist[i-1]+1, blacklist[i]});\n                }\n            }\n        }\n    }\n    \n    int pick() {\n        //Pick random interval\n        int idx = rand() % intervals.size();\n        int a = intervals[idx].first;\n        int b = intervals[idx].second;\n\n        //Pick random number in that interval\n        return a + (rand() % (b-a));\n    }\n};\n\n/**\n * Your Solution object will be instantiated and called as such:\n * Solution* obj = new Solution(n, blacklist);\n * int param_1 = obj->pick();\n */\n```
['C++']