1818. 绝对差值和

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import bisect 
class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        # 思想：max(abs(nums2旧[]-nums1旧[1])-abs(nums1新[]-nums2新[]))
        # abs(nums1新[]-nums2新[])要尽可能小，二分法找最近的位置；
        # 新形成的，带来的减少量最大化，可以使总和最小。
        n = len(nums1)
        total = sum([abs(x-y) for x,y in list(zip(nums1,nums2))])
        a = sorted(nums1)
        big_diff = 0
        for x,y in list(zip(nums1,nums2)):
            idx = bisect.bisect_left(a,y) # 找插入位置，如先前已被占，选左侧，但是没有插入！
            # 这里也不管离左边近还是右边近了，反正左右两边都比一遍。
            if idx<=n-1:
                big_diff = max(big_diff,abs(x-y)-abs(a[idx]-y))
            if idx>=1:
                big_diff = max(big_diff,abs(x-y)-abs(y-a[idx-1]))
        return (total-big_diff)%(10**9+7)