1818. Minimum Absolute Sum Difference

周賽復盤

這邊主要是要找到nums1 跟nums2的最大差值, 然後從nums1找一個數去替換, 看能不能讓sum變成極小

首先我們先遍歷兩個array, 找到這個差值最大的index,

令target = nums2[index]

然後我們對nums1先做sort, 然後用 binarysearch找這個target

整體時間複雜度為O(n logn)

如果不用估計會TLE

class Solution {
public:
    long arraydiff(vector<int> a, vector<int>b){
        long mod = 1e9 + 7;
        long res = 0;
        for(int i = 0 ; i < a.size();i++){
            res += labs(a[i] - b[i]);
        }
        return res % mod;
    }
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        if(nums1 == nums2) return 0;
        vector<int> t(nums1.begin(), nums1.end());
        sort(t.begin(), t.end());
        int maxdiff_idx = 0;
        int maxdiff_value = INT_MIN;
        for(int i = 0; i < nums1.size();i++){
            int diff = abs(nums1[i] - nums2[i]);
            if(diff > maxdiff_value){
                maxdiff_value = diff;
                maxdiff_idx = i;
            }
        }
        int target = nums2[maxdiff_idx];
        
        int l = 0;
        int r = t.size() - 1;
        int find;
        while(l <= r){
            int mid = (l + r) / 2;
            if(t[mid] == target){
                nums1[maxdiff_idx] = target;
                return arraydiff(nums1, nums2);
            }else if (t[mid] < target){
                l = mid + 1;
            }else if (t[mid] > target){
                r = mid - 1;
            }
        }
        int cloest_value = INT_MAX;
        if(l != nums1.size()){
            if(abs(t[l] - target) < cloest_value){
                cloest_value = abs(t[l] - target);
                find = t[l];
            }
        }
        if(r >= 0){
            if(abs(t[r] - target) < cloest_value){
                cloest_value = abs(t[r] - target);
                find = t[r];
            }
        }
        nums1[maxdiff_idx] = find;
        return arraydiff(nums1, nums2);
        
        
    }
};