題目連結:
題目意譯:
給定兩整數陣列 arr1 和 arr2,以及一整數 d,回傳兩個陣列之間的距離值。
距離值定義為元素 arr1[i] 的數量,其中這些元素滿足不存在任何一個元素 arr2[j] 使得 |arr1[i]-arr[j]| ≦ d。
限制:
1 ≦ arr1.length, arr2.length ≦ 500
-1000 ≦ arr1[i], arr2[j] ≦ 1000
0 ≦ d ≦ 100
範例測資:
範例 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
解題思維:
先把 arr2 中的整數由小到大排序。
接著我們便可以掃過 arr1 中的每個數字 arr1[i],然後利用二分搜尋法(Binary Search)來找到該數被 arr2 中哪兩個數字夾住(又或是 arr1[i] 大於/小於 arr2 中的所有數字),然後看這兩個離最近的數字是否與 arr1[i] 之值差 d 以上(不含)。
如果是的話,則 arr1[i] 就是一個我們要找的元素;反之則不是。最後統計過程中 arr1[i] 是我們要找的元素之數量即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。