D.二分查找-进阶——1385. 两个数组间的距离值

题目链接：1385. 两个数组间的距离值（简单）

算法原理：

大致思路与👇相同，这题还稍微简单些

D.二分查找-进阶——2300. 咒语和药水的成功对数

解法：二分查找

对于arr1中的每一个元素x，不符合题意的区间是[x-d,x+d]，所以可以对arr2排序进行二分来找最左端点x-d或者最右端点x+d

思路一：找最左端点模型解法

7ms击败38.02%

时间复杂度O(Nlogn)

找最左端点x-d，如果没有x-d那么最终left的位置是x-d右侧的

①如果该数小于x-d，说明此时left在最后一个位置，数组arr2中所有元素均小于x-d，自然符合题意，ret++

②如果该数大于x+d，说明此时left在第一个位置，数组arr2中所有元素均大于x+d，自然符合题意，ret++

思路二：找最右端点模型解法

7ms击败38.02%

时间复杂度O(Nlogn)

找最右端点x+d，如果没有x+d那么最终left的位置是x+d左侧的

其余均与思路一相同

Java代码：

class Solution { public int findTheDistanceValue(int[] arr1, int[] arr2, int d) { int n=arr2.length,ret=0; Arrays.sort(arr2); for(int x:arr1){ //找最左端点模型解法 int t=x-d; int left=0,right=n-1; while(left<right){ int mid=left+(right-left)/2; if(arr2[mid]<x-d) left=mid+1; else right=mid; } //arr2[left]<x-d:说明所有的数都比x-d小，全符合条件 //arr2[left]>x+d:说明所有的数都比x-d大，全符合条件 if(arr2[left]<x-d||arr2[left]>x+d) ret++; } return ret; } }

class Solution { public int findTheDistanceValue(int[] arr1, int[] arr2, int d) { int n=arr2.length,ret=0; Arrays.sort(arr2); for(int x:arr1){ //找最右端点模型解法 int t=x-d; int left=0,right=n-1; while(left<right){ int mid=left+(right-left+1)/2; if(arr2[mid]>x+d) right=mid-1; else left=mid; } //arr2[left]<x-d:说明所有的数都比x-d小，全符合条件 //arr2[left]>x+d:说明所有的数都比x-d大，全符合条件 if(arr2[left]<x-d||arr2[left]>x+d) ret++; } return ret; } }