LeetCode 解題筆記：1385. Find the Distance Value Between Two Arrays

作者：王一哲
日期：2026年11月5日


LeetCode 題目連結：1385. Find the Distance Value Between Two Arrays

解題想法

簡單題。題目給兩個陣列 $arr1, arr2$ 及一個整數 $d$，如果從 $arr1$ 之中取一個數字 $arr1[i]$，且在 $arr2$ 之中沒有任何一個數字符合 $|arr1[i] - arr2[j]| \leq d$ 則距離加 1，計算兩個陣列的距離為何？

可以先將 $arr2$ 排序。用一個 for 迴圈依序讀取 $arr1$ 的數值 $v$，用二分搜尋法工具例如 Python bisect_left 或是 C++ lower_bound 從 $arr2$ 之中找第一個大於、等於 $v$ 的值對應的索引值 $idx$，依據 $idx$ 的值計算兩者的差 $dist$，再計算距離。

Python 程式碼

Runtime: 3 ms, beats 97.78%. Memory: 19.36 MB, beats 36.40%.

from bisect import bisect_left

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr2.sort()
        m = len(arr2)
        ans = 0
        for v in arr1:
            idx = bisect_left(arr2, v)
            if idx == m:
                dist = v - arr2[-1]
            elif idx == 0:
                dist = arr2[0] - v
            else:
                dist = min(arr2[idx] - v, v - arr2[idx-1])
            if dist > d: ans += 1
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 16.37 MB, beats 98.94%.

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr2.begin(), arr2.end());
        int m = (int)arr2.size(), ans = 0;
        for(int v : arr1) {
            auto idx = lower_bound(arr2.begin(), arr2.end(), v) - arr2.begin();
            int dist;
            if (idx == m) {
                dist = v - arr2[m-1];
            } else if (idx == 0) {
                dist = arr2[0] - v;
            } else {
                dist = min(arr2[idx] - v, v - arr2[idx-1]);
            }
            if (dist > d) ans++;
        }
        return ans;
    }
};