• 欢迎光临~

lc1818. 绝对差值和

开发技术 开发技术 2022-10-02 次浏览

1818. 绝对差值和 - 力扣(LeetCode)

官方题解 绝对差值和 - 绝对差值和 - 力扣(LeetCode)

lc1818. 绝对差值和

 

 

wa的思路:

1、找绝对值差最大的位置maxi 然后取nums2[maxi]的值去有序的nums1[]里面二分查找

2、不处理二分边界值

3、不考虑返回位置中 相邻的另一个左数的绝对值差更小

ac方法:

先新建一个res数组用来存有序的nums1数组。

遍历nums1[],nums2[]每一个数,求nums1[i]-nums2[i]的绝对值,然后去二分查找num1中可替换nums1[i]的下标idx.

找到以后 如果idx不为0 就比较res[idx]和res[idx-1]替换nums1[i]哪个方案更好,将答案和ans比较后存入ans

如果idx==0就直接比较res[idx]替换nums1[i]的方案的值和ans哪个大

要注意不同的二分写法区别,我这题解是针对我的二分边界处理的

 

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int len = nums1.length;
        int[] res = new int[len];
        System.arraycopy(nums1,0,res,0,len);
        Arrays.sort(res);
        int sum = 0;
        int m = 1000000007;
        int ans = 0;
        int tp = 0;
        for(int i=0 ; i < len;++i){
            tp = Math.abs(nums1[i]-nums2[i]);
            sum = (sum + tp) % m;
            int idx = bSearch(res,nums2[i]);
          //  if(idx == len) idx = idx-1;
            if(idx!=0){
                ans = Math.max(ans,Math.max(Math.abs(nums2[i]-nums1[i])-Math.abs(nums2[i]-res[idx]),Math.abs(nums2[i]-nums1[i])-Math.abs(nums2[i]-res[idx-1])));
            }
            else {
                ans = Math.max(ans,Math.abs(nums2[i]-nums1[i])-Math.abs(nums2[i]-res[idx]));
            }
            
        }
        return (sum-ans+m)%m;
    }
    private int bSearch(int[] a,int num){
        int l = 0;
        int r = a.length-1;
        int mid = 0;
        while(l<r){
             mid = l + r >> 1;
             if(a[mid]<num)l = mid+1;
             else r = mid;
        }
        return r;
    }
}

 

 

class Solution {
    public int minAbsoluteSumDiff(int[] nums1int[] nums2) {
        int len = nums1.length;
        int[] res = new int[len];
        System.arraycopy(nums1,0,res,0,len);
        Arrays.sort(res);
        int sum = 0;
        int m = 1000000007;
        int ans = 0;
        int tp = 0;
        for(int i=0 ; i < len;++i){
            tp = Math.abs(nums1[i]-nums2[i]);
            sum = (sum + tp) % m;
            int idx = bSearch(res,nums2[i]);
          //  if(idx == len) idx = idx-1;
            if(idx!=0){
                ans = Math.max(ans,Math.max(Math.abs(nums2[i]-nums1[i])-Math.abs(nums2[i]-res[idx]),Math.abs(nums2[i]-nums1[i])-Math.abs(nums2[i]-res[idx-1])));
            }
            else {
                ans = Math.max(ans,Math.abs(nums2[i]-nums1[i])-Math.abs(nums2[i]-res[idx]));
            }
            
        }
        return (sum-ans+m)%m;
    }
    private int bSearch(int[] a,int num){
        int l = 0;
        int r = a.length-1;
        int mid = 0;
        while(l<r){
             mid = l + r >> 1;
             if(a[mid]<num)l = mid+1;
             else r = mid;
        }
        return r;
    }
}
程序员灯塔
转载请注明原文链接:lc1818. 绝对差值和
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com