关键词
绝对值，二分查找，上下界，TreeSet
题目描述
https://leetcode.com/problems/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
博主第一次提交的代码
查边界的地方代码还能优化，并且排序的这个方式感觉有点多余
class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int[] arr2Clone = arr2.clone();
Arrays.sort(arr2Clone);
for(int eachArr2: arr2){
if( eachArr2 < min){
min = eachArr2;
}
if( eachArr2 > max){
max = eachArr2;
}
}
int result = 0;
for(int eachArr1: arr1){
if( (eachArr1 - max > d ) || (min - eachArr1 > d ) ) {
result++;
}
for(int i = 0 ; i < arr2Clone.length - 1; i++){
if( (eachArr1 - arr2Clone[i]) > d && (arr2Clone[i+1] - eachArr1) > d ){
result++;
}
}
}
return result;
}
}
其他人优秀的代码
class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
int res = 0;
TreeSet<Integer> ts = new TreeSet<>();
for(int n : arr2)
ts.add(n);
for(int n : arr1){
Integer higher = ts.ceiling(n);
Integer lower = ts.floor(n);
int diff = 0;
if(higher == null){
diff = Math.abs(lower - n);
}else if(lower == null){
diff = Math.abs(higher - n);
}else{
diff = Math.min(higher - n, n - lower);
}
if(diff > d)
res++;
}
return res;
}
}
