comments | difficulty | edit_url | rating | source | tags | ||||
---|---|---|---|---|---|---|---|---|---|
true |
简单 |
1234 |
第 22 场双周赛 Q1 |
|
给你两个整数数组 arr1
, arr2
和一个整数 d
,请你返回两个数组之间的 距离值 。
「距离值」 定义为符合此距离要求的元素数目:对于元素 arr1[i]
,不存在任何元素 arr2[j]
满足 |arr1[i]-arr2[j]| <= d
。
示例 1:
输入:arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2 输出:2 解释: 对于 arr1[0]=4 我们有: |4-10|=6 > d=2 |4-9|=5 > d=2 |4-1|=3 > d=2 |4-8|=4 > d=2 所以 arr1[0]=4 符合距离要求 对于 arr1[1]=5 我们有: |5-10|=5 > d=2 |5-9|=4 > d=2 |5-1|=4 > d=2 |5-8|=3 > d=2 所以 arr1[1]=5 也符合距离要求 对于 arr1[2]=8 我们有: |8-10|=2 <= d=2 |8-9|=1 <= d=2 |8-1|=7 > d=2 |8-8|=0 <= d=2 存在距离小于等于 2 的情况,不符合距离要求 故而只有 arr1[0]=4 和 arr1[1]=5 两个符合距离要求,距离值为 2
示例 2:
输入:arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3 输出:2
示例 3:
输入:arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6 输出:1
提示:
1 <= arr1.length, arr2.length <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100
我们可以先对数组
时间复杂度
class Solution:
def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
arr2.sort()
ans = 0
for x in arr1:
i = bisect_left(arr2, x - d)
ans += i == len(arr2) or arr2[i] > x + d
return ans
class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
Arrays.sort(arr2);
int ans = 0;
for (int x : arr1) {
int i = Arrays.binarySearch(arr2, x - d);
i = i < 0 ? -i - 1 : i;
if (i == arr2.length || arr2[i] > x + d) {
++ans;
}
}
return ans;
}
}
class Solution {
public:
int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
ranges::sort(arr2);
int ans = 0;
for (int x : arr1) {
auto it = ranges::lower_bound(arr2, x - d);
if (it == arr2.end() || *it > x + d) {
++ans;
}
}
return ans;
}
};
func findTheDistanceValue(arr1 []int, arr2 []int, d int) (ans int) {
sort.Ints(arr2)
for _, x := range arr1 {
i := sort.SearchInts(arr2, x-d)
if i == len(arr2) || arr2[i] > x+d {
ans++
}
}
return
}
function findTheDistanceValue(arr1: number[], arr2: number[], d: number): number {
arr2.sort((a, b) => a - b);
let ans: number = 0;
for (const x of arr1) {
const i = _.sortedIndex(arr2, x - d);
if (i === arr2.length || arr2[i] > x + d) {
++ans;
}
}
return ans;
}
impl Solution {
pub fn find_the_distance_value(arr1: Vec<i32>, mut arr2: Vec<i32>, d: i32) -> i32 {
arr2.sort();
let mut ans = 0;
for &x in &arr1 {
let i = match arr2.binary_search(&(x - d)) {
Ok(j) => j,
Err(j) => j,
};
if i == arr2.len() || arr2[i] > x + d {
ans += 1;
}
}
ans
}
}