From simple to deluxe, evolution of abstraction and c++ solutions


  • 0

    Simple solution, nested binary searches:

    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int l, r;
        for (l = 0, r = nums.back() - nums.front(); l < r;) {
            int m = l + (r - l) / 2, s = 0;
            for (int i = 0; i < nums.size(); i++) {
                int l2, r2, t = nums[i] + m;
                for (l2 = i, r2 = nums.size(); l2 < r2;) {
                    int m2 = l2 + (r2 - l2) / 2;
                    if (nums[m2] <= t)
                        l2 = m2 + 1;
                    else
                        r2 = m2;
                }
                s += l2 - i - 1;
            }
            if (s < k)
                l = m + 1;
            else
                r = m;
        }
        return l;
    }
    

    Reinvent the binary_search stl function:

    template<class Compare>
    int binary_search(int first, int last, Compare cmp) {
        while (first < last) {
            int mid = first + (last - first) / 2;
            if (cmp(mid))
                first = mid + 1;
            else
                last = mid;
        }
        return first;
    }
    
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return binary_search(0, nums.back() - nums.front(), [&](int m) {
            int s = 0;
            for (int i = 0; i < nums.size(); i++)
                s += binary_search(i, nums.size(), [&](int m2) {
                    return nums[m2] <= nums[i] + m;
                }) - i - 1;
            return s < k;
        });
    }
    

    One step further:

    template<class Compare>
    int binary_search(int first, int last, Compare cmp) {
        while (first < last) {
            int mid = first + (last - first) / 2;
            if (cmp(mid))
                first = mid + 1;
            else
                last = mid;
        }
        return first;
    }
    
    template<class Data, class T>
    int lower_bound(Data &data, int first, int last, T val) {
        return binary_search(first, last, [&](int mid) {
            return data[mid] < val;
        });
    }
    
    template<class Data, class T>
    int upper_bound(Data &data, int first, int last, T val) {
        return binary_search(first, last, [&](int mid) {
            return !(val < data[mid]);
        });
    }
    
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return binary_search(0, nums.back() - nums.front(), [&](int m) {
            int s = 0;
            for (int i = 0; i < nums.size(); i++)
                s += upper_bound(nums, i, nums.size(), nums[i] + m) - i - 1;
            return s < k;
        });
    }
    

Log in to reply
 

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