两个数组间的距离值
解题思路：
-
题意可以理解为：求 arr1 中与 arr2 所有元素之差绝对值大于 D 的元素个数；
-
将 arr2 排序，寻找 arr1 中的元素在 arr2 中的位置；
- 如果左边位置和右边位置的元素都满足 | arr1[i] - arr2[i] | > d，则全部满足要求，结果++；
- 反之则不满足；
图解：
复杂度：
-
时间复杂度：O((n+m)logm)；
- 假设 arr1 中元素个数为 n，arr2 中元素个数为 m；
- 给 arr2 排序的时间代价是 O(mlogm)，对于 arr1 中的每个元素都在 arr2 中二分的时间代价是 O(nlogm)，故渐进时间复杂度为 O((n+m)logm)；
-
空间复杂度：O(1)；
代码实现：
var findTheDistanceValue = function (arr1, arr2, d) {
arr2.sort((a, b) => a - b);
let res = 0;
for (let i = 0; i < arr1.length; i++) {
let tmp = true;
let inx = searchInx(arr2, arr1[i]);
if (inx - 1 >= 0) {
tmp = tmp & Math.abs(arr1[i] - arr2[inx - 1]) > d;
}
if (inx < arr2.length) {
tmp = tmp & Math.abs(arr1[i] - arr2[inx]) > d;
}
if (tmp) res++;
}
return res;
};
var searchInx = function (arr2, i) {
let left = 0;
let right = arr2.length - 1;
while (left <= right) {
let mid = left + (right - left) >> 1;
if (arr2[mid] < i) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
367.有效的完全平方数
上一篇
评论
