力扣刷题 day39：10-09

1.统计有序矩阵中的负数

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。 请你统计并返回 grid 中 负数 的数目。

方法一：二分法 

#方法一：二分法
def countNegatives(grid):
    res=0
    for nums in grid:
        left,right=0,len(nums) -1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]>=0:
                left=mid+1    #找到第一个负数所在的下标
            elif nums[mid] < 0:
                right=mid-1
        res+=len(nums)-left
    return res

2.两个数组间的距离值

给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。

「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。

方法一：二分法 

#方法一：二分法
def findTheDistanceValue(arr1,arr2,d):
    arr2=sorted(arr2) #先排序
    res=0
    for i in arr1:
        left,right=0,len(arr2)-1
        while left<=right:
            mid=(left+right)//2
            if arr2[mid]>i:
                right=mid-1
            else:
                left=mid + 1
        if right<0: 
            if arr2[0]-i>d:
                res+=1
        elif left>len(arr2)-1:
            if i-arr2[-1]>d:
                res+=1
        elif arr2[left]-i>d and i-arr2[right]>d :
            res+=1 #最小间距都满足题意
    return res