[C++] DO NOT use rand() after C++11 !
It is not recommand to use rand() when N is large.\nhttps://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution\n\nOther solutions which use rand(
It is not recommand to use `rand()` when N is large.\nhttps://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution\n\nOther solutions which use `rand()/M` are wrong. \n`rand()` generates random numbers in [0, RAND_MAX], where `RAND_MAX` depends on the complier.\nUsually, `RAND_MAX` is 32767 (in leetcode it is 2147483647), which could not generate numbers larger than it. In this problem, `N` could be 1000000000, so we cannot directly use `rand()/M` here.\n\nAnother problem is, even if N is less than 10000, it is also not accurate to use `rand()/M`.\nFor example, use `rand()/10000` to generate numbers in [0,9999]. It is more likely to generate a number in [0, 2767] than in [2868, 9999]:\n```\n[0,2767] % 10000->[0,2767]\n[2768,9999] % 10000->[2768,9999]\n[10000,12767] % 10000->[0,2767]\n[12768,19999] % 10000->[2768,9999]\n[20000,22767] % 10000->[0,2767]\n[22768,29999] % 10000->[2768,9999]\n[30000,32767] % 10000->[0,2767]\n```\n\nHere is my code, O(b log b) construction and O(log b) pick. (not the fastest, see other solutions)\n\n```\nclass Solution {\npublic:\n    vector<int> v;\n    std::mt19937 gen;\n    std::uniform_int_distribution<> dis;\n    Solution(int N, vector<int> blacklist) {\n        v = blacklist;\n        sort(v.begin(), v.end());\n        v.push_back(N);\n        for (int i = 0; i < v.size(); i++) v[i] -= i;\n        \n        std::random_device rd;  //Will be used to obtain a seed for the random number engine\n        gen = std::mt19937(rd()); //Standard mersenne_twister_engine seeded with rd()\n        dis = std::uniform_int_distribution<>(0, N - v.size());\n    }\n    \n    int pick() {\n        int rnd = dis(gen);\n        auto it = upper_bound(v.begin(), v.end(), rnd) - 1;\n        int idx = it - v.begin();\n        return idx + rnd + 1;\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```
[]