Share my C++ solution, O(lg(n)) to pick, O(nlg(n)) for sorting

  • 6

    Pre-process sorting for O(nlg(n))
    Pick in O(lg(n)) using binary search
    O(n) space to store value/index pairs

    class Solution {
        typedef pair<int, int> pp; // <value, index>
        static bool comp(const pp& i, const pp& j) { return (i.first < j.first); }
        vector<pp> mNums;
        Solution(vector<int> nums) {
            for(int i = 0; i < nums.size(); i++) {
                mNums.push_back(pp({nums[i], i}));
            sort(mNums.begin(), mNums.end(), comp);
        int pick(int target) {
            pair<vector<pp>::iterator, vector<pp>::iterator> bounds = equal_range(mNums.begin(), mNums.end(), pp({target,0}), comp);
            int s = bounds.first - mNums.begin();
            int e = bounds.second - mNums.begin();
            int r = e - s;
            return mNums[s + (rand() % r)].second;

  • 0

    Nice Solution! But can you give some brife explanation? I do the sort first, but I don't know where is your binary search? Please, just write some comment.

  • 0

    @dader the binary search is done by equal_range()

  • 0

    I get a cryptic compile error, can you check?

    required from 'std::pair<_FIter, _FIter> std::__equal_range(_ForwardIt
    erator, _ForwardIterator, const _Tp&, _CompareItTp, _CompareTpIt) [wit
    h _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*
    , std::vector<std::pair<int, int> > >; _Tp = std::pair<int, int>; _Com
    pareItTp = __gnu_cxx::__ops::_Iter_comp_val<bool (*)(std::pair<int, in
    t>&, std::pair<int, int>&)>; _CompareTpIt = __gnu_cxx::__ops::_Val_com
    p_iter<bool (*)(std::pair<int, int>&, std::pair<int, int>&)>]'

  • 0

    @StefanPochmann oops, I posted wrong one, the arguments of comp() should be const
    I've fixed it in original post, thanks

        static bool comp(const pp& i, const pp& j) { return (i.first < j.first); }

  • 0

    @chin-heng Man, g++ is so smart when it comes to optimizing code for speed, but so dumb when it comes to optimizing error messages for readability. Why couldn't it just say "the arguments of comp() should be const" like you did :-)

  • 4

    A Python version:

    class Solution(object):
        def __init__(self, nums):
            self.sorted = sorted(zip(nums, range(len(nums))))
        def pick(self, target):
            start = bisect.bisect_left(self.sorted, (target,))
            stop = bisect.bisect_left(self.sorted, (target + 1,))
            return self.sorted[random.randrange(start, stop)][1]

  • 0

    @StefanPochmann took me some time decoding when I first got the error message...

  • 1

    Nice solution! I think there may be opportunity for clean up, if I may suggest :-)

    auto bounds = equal_range(...)
    // The number of equal items is this:
    auto N = distance(bounds.first, bounds.second);
    // Could short-circuit if N == 1
    if(N == 1)
      return bounds.first->second;
    // For return, can index off the bounds iterator:
    return bounds.first[rand() % N].second;

  • 0

    Tried submitting your Python version a few times, but I kept getting MLE on the 13th test case :(
    Perhaps the limits have been adjusted

  • 0

    Nice solution, although function pick can be simplified as:

    int pick(int target) {
        auto bounds = equal_range(mNums.begin(), mNums.end(), pp({target,0}), comp);
        return (bounds.first+rand()%(bounds.second-bounds.first))->second;

Log in to reply

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