Easy

题目描述

给你两个整数数组 arr1 和 arr2，以及一个整数 d，请你返回两个数组之间的距离值。

距离值定义为：统计 arr1 中的元素 arr1[i]，使得不存在任何 arr2 中的元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d。

示例 1：

输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
输出：2
解释：
对于 arr1[0]=4，我们有：
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
对于 arr1[1]=5，我们有：
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
对于 arr1[2]=8，我们有：
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2

示例 2：

输入：arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
输出：2

示例 3：

输入：arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
输出：1

提示：

  • 1 <= arr1.length, arr2.length <= 500
  • -1000 <= arr1[i], arr2[j] <= 1000
  • 0 <= d <= 100

解题思路

解题思路

这道题要求统计 arr1 中有多少元素不与 arr2 中任何元素的差值小于等于 d。

方法一：暴力解法

对于 arr1 中的每个元素，检查它与 arr2 中所有元素的距离是否都大于 d。如果是，计数加一。

方法二：排序 + 二分查找（推荐）

先对 arr2 进行排序，然后对于 arr1 中的每个元素 x，使用二分查找找到 arr2 中最接近 x 的元素。具体来说：

  1. 找到第一个大于等于 x 的元素位置
  2. 检查该位置及前一个位置的元素与 x 的距离
  3. 如果这两个最近的元素与 x 的距离都大于 d，说明 arr2 中所有元素与 x 的距离都大于 d

这种方法的时间复杂度为 O(n log n + m log n)，其中 n 是 arr2 的长度，m 是 arr1 的长度。

方法三：集合查找

将 arr2 转换为集合，然后对于 arr1 中的每个元素 x，检查范围 [x-d, x+d] 内是否存在 arr2 中的元素。

代码实现

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr2.begin(), arr2.end());
        int count = 0;
        
        for (int x : arr1) {
            auto it = lower_bound(arr2.begin(), arr2.end(), x);
            bool valid = true;
            
            // Check the element at position it (first >= x)
            if (it != arr2.end() && abs(*it - x) <= d) {
                valid = false;
            }
            
            // Check the element before it (largest < x)
            if (valid && it != arr2.begin()) {
                --it;
                if (abs(*it - x) <= d) {
                    valid = false;
                }
            }
            
            if (valid) count++;
        }
        
        return count;
    }
};

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr2.sort()
        count = 0
        
        for x in arr1:
            left, right = 0, len(arr2)
            
            # Binary search for the first element >= x
            while left < right:
                mid = (left + right) // 2
                if arr2[mid] < x:
                    left = mid + 1
                else:
                    right = mid
            
            valid = True
            
            # Check the element at position left (first >= x)
            if left < len(arr2) and abs(arr2[left] - x) <= d:
                valid = False
            
            # Check the element before left (largest < x)
            if valid and left > 0 and abs(arr2[left - 1] - x) <= d:
                valid = False
            
            if valid:
                count += 1
        
        return count

public class Solution {
    public int FindTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Array.Sort(arr2);
        int count = 0;
        
        foreach (int x in arr1) {
            int left = 0, right = arr2.Length;
            
            // Binary search for the first element >= x
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (arr2[mid] < x) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            bool valid = true;
            
            // Check the element at position left (first >= x)
            if (left < arr2.Length && Math.Abs(arr2[left] - x) <= d) {
                valid = false;
            }
            
            // Check the element before left (largest < x)
            if (valid && left > 0 && Math.Abs(arr2[left - 1] - x) <= d) {
                valid = false;
            }
            
            if (valid) count++;
        }
        
        return count;
    }
}

var findTheDistanceValue = function(arr1, arr2, d) {
    arr2.sort((a, b) => a - b);
    let count = 0;
    
    for (let x of arr1) {
        let left = 0, right = arr2.length;
        
        // Binary search for the first element >= x
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (arr2[mid] < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        let valid = true;
        
        // Check the element at position left (first >= x)
        if (left < arr2.length && Math.abs(arr2[left] - x) <= d) {
            valid = false;
        }
        
        // Check the element before left (largest < x)
        if (valid && left > 0 && Math.abs(arr2[left - 1] - x) <= d) {
            valid = false;
        }
        
        if (valid) count++;
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
暴力解法O(m × n)O(1)
排序 + 二分查找O(n log n + m log n)O(1)
集合查找O(n + m × d)O(n)

其中 m 是 arr1 的长度，n 是 arr2 的长度。推荐使用排序 + 二分查找的方法。