LeetCode 1385. Find the Distance Value Between Two Arrays-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 1385. Find the Distance Value Between Two Arrays。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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] <= 1000
0 <= d <= 100

这题第一反应就是读不懂题，第二反应就是不会做，嗯，看了答案确实如同大家所说的这道题的表述绝对有点问题，太绕了！已经不想解释这道题到底想让我干嘛了毕竟现在脑子已经不清醒了……大概就是要在另一个数组里找对于某个数字来说，是不是所有数字和这个数字的绝对值之差都大于一个数。

于是就可以转换成二分查找的思想，找到在这个数组里这个数字应该插在哪儿，并比较离他最近的两个数字和它的绝对值之差看是不是都大于d，如果都大于那就符合条件。

于是就艰难地写了个二分，历尽千辛万苦凭借一己之力和一些些看小笔记发现愚蠢错误，最后写出来了，啊。几个愚蠢错误：

1. end = arr.length - 1忘了- 1

2. num < arr[mid] 忘了arr[]

3. 这道题绕来绕去的大于小于也傻傻分不清

对于二分插入的思想我写在二分大总结里了：LeetCode 704. Binary Search_wenyq7的博客-CSDN博客

精华思想就在于，还是用low <= high的判断条件，最后的顺序是high, num, low。

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，机智，只要记得还有这个数据结构能用就行，真懒得花时间了：LeetCode - The World's Leading Online Programming Learning Platform文章来源地址https://www.toymoban.com/news/detail-688079.html

到了这里，关于LeetCode 1385. Find the Distance Value Between Two Arrays的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！