Given two integer arrays?arr1?and?arr2, and the integer?d,?return the distance value between the two arrays.
The distance value is defined as the number of elements?arr1[i]?such that there is not any element?arr2[j]?where?|arr1[i]-arr2[j]| <= d.
Example 1:
Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2 Output: 2 Explanation: For arr1[0]=4 we have: |4-10|=6 > d=2 |4-9|=5 > d=2 |4-1|=3 > d=2 |4-8|=4 > d=2 For arr1[1]=5 we have: |5-10|=5 > d=2 |5-9|=4 > d=2 |5-1|=4 > d=2 |5-8|=3 > d=2 For arr1[2]=8 we have: |8-10|=2 <= d=2 |8-9|=1 <= d=2 |8-1|=7 > d=2 |8-8|=0 <= d=2
Example 2:
Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3 Output: 2
Example 3:
Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6 Output: 1
Constraints:
1 <= arr1.length, arr2.length <= 500-1000 <= arr1[i], arr2[j] <= 10000 <= d <= 100
這題第一反應(yīng)就是讀不懂題，第二反應(yīng)就是不會做，嗯，看了答案確實(shí)如同大家所說的這道題的表述絕對有點(diǎn)問題，太繞了！已經(jīng)不想解釋這道題到底想讓我干嘛了畢竟現(xiàn)在腦子已經(jīng)不清醒了……大概就是要在另一個數(shù)組里找對于某個數(shù)字來說，是不是所有數(shù)字和這個數(shù)字的絕對值之差都大于一個數(shù)。
于是就可以轉(zhuǎn)換成二分查找的思想，找到在這個數(shù)組里這個數(shù)字應(yīng)該插在哪兒，并比較離他最近的兩個數(shù)字和它的絕對值之差看是不是都大于d，如果都大于那就符合條件。
于是就艱難地寫了個二分，歷盡千辛萬苦憑借一己之力和一些些看小筆記發(fā)現(xiàn)愚蠢錯誤，最后寫出來了，啊。幾個愚蠢錯誤：
1. end = arr.length - 1忘了- 1
2. num < arr[mid] 忘了arr[]
3. 這道題繞來繞去的大于小于也傻傻分不清
對于二分插入的思想我寫在二分大總結(jié)里了：LeetCode 704. Binary Search_wenyq7的博客-CSDN博客
精華思想就在于，還是用low <= high的判斷條件，最后的順序是high, num, low。文章來源：http://www.zghlxwxcb.cn/news/detail-688079.html
class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
int result = 0;
Arrays.sort(arr2);
for (int i : arr1) {
if (allLarger(i, arr2, d)) {
result++;
}
}
return result;
}
private boolean allLarger(int num, int[] arr, int d) {
// find the position i for num to insert into arr
// then check if the diff between (arr[i - 1] and arr[i + 1]) and num > d
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (num > arr[mid]) {
start = mid + 1;
} else if (num < arr[mid]) {
end = mid - 1;
} else {
return 0 > d;
}
}
// end start
if (end < 0) {
return arr[0] - num > d;
}
if (start > arr.length - 1) {
return num - arr[arr.length - 1] > d;
}
return (num - arr[end] > d) && (arr[start] - num > d);
}
}以及看到有人直接用了TreeSet，機(jī)智，只要記得還有這個數(shù)據(jù)結(jié)構(gòu)能用就行，真懶得花時間了：LeetCode - The World's Leading Online Programming Learning Platform文章來源地址http://www.zghlxwxcb.cn/news/detail-688079.html
到了這里，關(guān)于LeetCode 1385. Find the Distance Value Between Two Arrays的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
