【Leetcode Daily】1385两个数组间的距离值

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给两个数组，求一个数组在另一数组不满足与其中一个值的一定区间内的元素数量。

思路分享

• 如何实现二分可看【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置。

• 重点在于深刻理解二分的含义，比如上面样例的二分返回的下标的含义，其实是第一个大于目标值的下标，在这个基础上，如何该值同时已经超过目标值的区间，就说明满足题意。

  https://leetcode.cn/problems/find-the-distance-value-between-two-arrays/solutions/3010185/liang-chong-fang-fa-er-fen-cha-zhao-san-15u9b/

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    int lowerBound(vector<int> &nums, int tar) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left+(right-left)/2;
            if (nums[mid] < tar) {
                left = mid+1;
            }
            else {
                right = mid;
            }
        }
        return left; 
    }
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr2.begin(), arr2.end());
        int ans = 0;
        for (const int & i : arr1) {
            int index = lowerBound(arr2, i-d);
            if (index == arr2.size() || arr2[index] > i + d) {
                ans+=1;
            }
        }
        return ans;
    }
};