lc1818. 绝对差值和

标签：idx int res 绝对 差值 ans lc1818 nums1 nums2

1818. 绝对差值和 - 力扣（LeetCode）

官方题解 绝对差值和 - 绝对差值和 - 力扣（LeetCode）

 

 

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[] 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;     } }

标签：idx,int,res,绝对,差值,ans,lc1818,nums1,nums2
From： https://www.cnblogs.com/h404nofound/p/16749830.html