C++ counting sort, O(n) ctor, O(1) pick


  • 0
    A

    Memory complexity O(2*n) at worst.
    Unfortunately in most testcases, there are far less pick() calls than the length of numbers, which effectively inhibits the power of O(1) pick.

    13 / 13 test cases passed
    Status: Accepted
    Runtime: 235 ms

    class Solution {
    protected:
        vector<int> sorted;
        unordered_map<int, uint> cnt;
    public:
        Solution(vector<int> nums) {
            uint siz = nums.size(), accu = 0;
            sorted.resize(siz);
            cnt.reserve(siz);
            for (int n : nums) cnt[n]++;
            for (auto& p : cnt)  { accu += p.second; p.second = accu; }
            for (uint i = 0; i < siz; i++) sorted[--cnt[nums[i]]] = i;
        }
        
        int pick(int target) {
            auto it = cnt.find(target), nit = next(it);
            uint b = it->second, e = nit == cnt.end() ? cnt.size() : nit->second;
            return sorted[rand() % (e - b) + b];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.