Simple O(Nlog(max(a[i]))) solution using binary search


  • 5
    E

    Find the smallest number ans such that ans is not smaller than at least k differences. For each test value of ans, counting the number of differences not more than ans is done in linear time using two pointer method.

    class Solution {
    public:
        int smallestDistancePair(vector<int>& a, int k) {
            sort(a.begin(), a.end());
            int n = a.size(), lo = 0, hi = a[n-1] - a[0], ans = -1;
            while (lo <= hi) {
                int cnt = 0, j = 0, md = (lo + hi)/2;
                for (int i = 0; i < n; ++i) {
                    while (j < n && a[j] - a[i] <= md) ++j;
                    cnt += j - i-1;
                }
                if (cnt >= k) {
                    ans = md;
                    hi = md - 1;
                }
                else lo = md + 1;
            }
            
            return ans;
        }
    };
    

  • 0
    Z

    ty,nice one.


Log in to reply
 

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