LeetCode 1385. Find the Distance Value Between Two Arrays

, , ,

Question

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

Solution

因为是第一题，一般不会难，只需要认真读题目。

题目定义两个数组，假设包含m和n个元素。即m中任意一个都需要和n个数做绝对差值，然后看m中有多少个与全部n元素的差值大于d，则结果加1。其中可以优化的地方则是一旦找到小于等于d的情况就break，停止继续计算。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// time:O(mn) space:O(1);
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        if (arr1 == null || arr2 == null) return 0;
        int n = arr1.length, m = arr2.length;
        int countMax = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int diff = Math.abs(arr1[i] - arr2[j]);
                if (diff <= d) {
                    countMax++;
                    break;
                }
            }
        }
        return n - countMax;
    }