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
Constraints:
1 <= arr1.length, arr2.length <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100
Solution 1: All pairs
Time complexity: O(m*n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) { int ans = 0; for (int x : arr1) { bool flag = true; for (int y : arr2) if (abs(x - y) <= d) { flag = false; break; } ans += flag; } return ans; } }; |
Python3
1 2 3 4 |
# Author: Huahua class Solution: def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int: return sum(all(abs(x - y) > d for y in arr2) for x in arr1) |
Solution 2: Two Pointers
Sort arr1 in ascending order and sort arr2 in descending order.
Time complexity: O(mlogm + nlogn + m + n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) { sort(begin(arr1), end(arr1)); sort(rbegin(arr2), rend(arr2)); int ans = 0; for (int a : arr1) { while (arr2.size() && arr2.back() < a - d) arr2.pop_back(); ans += arr2.empty() || arr2.back() > a + d; } return ans; } }; |
Solution 3: Binary Search
Sort arr2 in ascending order. and do two binary searches for each element to determine the range of [a-d, a+d], if that range is empty we increase the counter
Time complexity: O(mlogm + nlogm)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) { sort(begin(arr2), end(arr2)); int ans = 0; for (int a : arr1) { auto it1 = lower_bound(begin(arr2), end(arr2), a - d); auto it2 = upper_bound(begin(arr2), end(arr2), a + d); if (it1 == it2) ++ans; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment