# 1818. Minimum Absolute Sum Difference
###### tags: `Leetcode` `Medium` `Binary Search`
Link: https://leetcode.com/problems/minimum-absolute-sum-difference/description/
## 思路
对于每一个idx i，用binary search找到nums1里面最接近nums2[i]的element 然后替换 算出absolute sum difference 取最小的一个就是答案
方法一是先算出original的absolute sum difference 然后一个idx一个idx尝试 算出替换后的absolute sum difference
方法二是只遍历一遍 在过程中算出original sum difference 每次比较gain (```abs(nums1[i]-nums2[i])-替换后的absolute difference```) 找到最大的gain 答案是original-gain
## Code
方法一

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length, mod = 1000000007;
        long original = 0;
        for(int i=0; i<n; i++) original += Math.abs(nums1[i]-nums2[i]);
        int[] arr = nums1.clone();
        Arrays.sort(arr);
        long ans = original;
        for(int i=0; i<n; i++){
            int idx = binarySearch(arr, nums2[i]);
            if(idx!=n) ans = Math.min(ans, original-(Math.abs(nums1[i]-nums2[i]))+Math.abs(arr[idx]-nums2[i]));
            if(idx!=0) ans = Math.min(ans, original-(Math.abs(nums1[i]-nums2[i]))+Math.abs(arr[idx-1]-nums2[i]));
        }
        return (int)(ans%mod);
    }
    public int binarySearch (int[] arr, int num){
        int start = 0, end = arr.length;
        while(start<end){
            int mid = start+(end-start)/2;
            if(arr[mid]<num) start = mid+1;
            else end = mid;
        }
        return start;
    }
}

方法二

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length, mod = 1000000007;
        long original = 0, maxDecrement = 0;
        int[] arr = nums1.clone();
        Arrays.sort(arr);
        for(int i=0; i<n; i++){
            int currDiff = Math.abs(nums1[i]-nums2[i]);
            original += currDiff;
            int idx = binarySearch(arr, nums2[i]);
            if(idx!=n) maxDecrement = Math.max(maxDecrement, currDiff-Math.abs(arr[idx]-nums2[i]));
            if(idx!=0) maxDecrement = Math.max(maxDecrement, currDiff-Math.abs(arr[idx-1]-nums2[i]));
        }
        return (int)((original-maxDecrement)%mod);
    }
    public int binarySearch (int[] arr, int num){
        int start = 0, end = arr.length;
        while(start<end){
            int mid = start+(end-start)/2;
            if(arr[mid]<num) start = mid+1;
            else end = mid;
        }
        return start;
    }
}