美文网首页LeetCode个人题解
LeetCode | 1385. Find the Distan

LeetCode | 1385. Find the Distan

作者: Wonz | 来源:发表于2020-03-22 09:47 被阅读0次

    LeetCode 1385. Find the Distance Value Between Two Arrays两个数组间的距离值【Easy】【Python】【暴力】

    Problem

    LeetCode

    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

    问题

    力扣

    给你两个整数数组 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[1]=5 我们有:
    |5-10|=5 > d=2 
    |5-9|=4 > d=2 
    |5-1|=4 > d=2 
    |5-8|=3 > d=2
    对于 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 = [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

    思路

    暴力

    时间复杂度: O(n^2)
    空间复杂度: O(1)

    Python3代码
    from typing import List
    
    class Solution:
        def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
            # solution one: 暴力
            res = 0
            for x in arr1:
                cnt = 0
                for y in arr2:
                    if abs(x-y) <= d:
                        break
                    else:
                        cnt += 1
                    if cnt == len(arr2):
                        res += 1
            return res
    
            # solution two: 一行代码
            return sum(all(abs(a1 - a2) > d for a2 in arr2) for a1 in arr1)
    

    GitHub链接

    Python

    相关文章

      网友评论

        本文标题:LeetCode | 1385. Find the Distan

        本文链接:https://www.haomeiwen.com/subject/ojdmyhtx.html