二分查找的妙用


  • 0
    X
    class Solution {
    public:
    int smallestDistancePair(vector<int>& nums, int k) {
    
        sort(nums.begin(), nums.end());
        
        // 得到最小和最大距离
        int low = 1e+6;
        int len = nums.size();
        for (int i = 1; i < len; i++) {
            low = min(low, nums[i] - nums[i - 1]);
        }
        int high = nums[len - 1] - nums[0];
        
        // 二分查找
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (countPairs(nums, mid) < k)
                low = mid + 1;
            else
                high = mid;
        }
        return low;
    }
    
    // 任给一个数求出他是距离数组中的第几个(距离小于他的有几个)
    int countPairs(vector<int>& nums, int mid) {
        int loc = 0;
        int len = nums.size();
        for (int i = 0; i < len; i++) {
           // int j = i;  // 保证不重复,内部循环从i开始且只算到i的距离
           // while (j < len && nums[j] - nums[i] <= mid) j++;  // 小于等于mid!!!这样才能得到重复距离的第一个
            int j = UpperBound(nums, i, mid);
            loc += j - i - 1; 
        }
        return loc;
    }
    
    // 求j也可以用二分查找的方式
    int UpperBound(vector<int>& nums, int i, int dis) {
        int len = nums.size();
        int low = i;
        int high = len - 1;
        if (nums[high] - nums[low] <= dis)  // 这里必须加上此判断,因为在此情况下j大小应该是len!
            return high + 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] - nums[i] <= dis)
                low = mid + 1;
            else
                high = mid;
        }
        return low;
    }
    };
    
    /*
    先将数组排序,然后得到最小距离和最大距离
    求距离数组的第k小,不需要知道距离数组具体内部是啥,(距离数组中的每个数都可以算出来,但是没必要运算**任给一个数,可以求出它在距离数组中是第几个***)
    因此使用二分查找,找到第k小
    
    第32行,若当j=len-1时还是满足条件,则应将j置为len,因为这里的意思是j所处的位置是第一个与nums[i]距离大于mid的位置。第34行算距离小于mid个数的时候是不算上i到j的距离的(多减了个1),因此第44行也应加上这种判断
    */

Log in to reply
 

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