1818. 絕對差值和 前言：

這題其實挺簡單的，我的簡單意思是，他可以用簡單粗暴的方法做，那么用這種方法做呢，肯定是要用雙循環的，那么時間復雜度就是O(nn)，那對于這一題的要求來說，對不起，你必定超時（別問我怎么知道，因為我試過）。

因此對于找替換元素那里的雙循環，用二分查找，就可以省一點時間，時間復雜度就可以控制在：O(nlogn)，這樣子就不會超時啦

貼個題目：

貼個示例：

解題思路：

首先，看到題目，讓我們算一個nums1[i]-nums2[i]的和，但是！有一個條件：

nums1中可以用一個元素覆蓋另一個元素，但是，只能覆蓋一次

而且這個覆蓋能讓求和的值為最小的

根據這個條件，我們明白兩點：

1、只能換一次

2、而且換了之后求和為最小的

因此，我們需要nums1[j]-nums2[I]的對應每一個nums2[I]的最小值

然后由公式：

abs(nums1[i]-nums2[i])-abs(nums1[min]-nums2[i]

知道前一項abs()為定值，因此求這一個公式的最大值，就是求上述的最小值

我用一個數組maxdiff_arr存放這個公式的值

然后找出這個數組的最大值，返回其下標就是我要求的覆蓋后的最小值

最后遍歷nums1和nums2，一個一個加上去得到和就是正確答案了

如果這里不明白的話，嘗試看一下代碼，有詳細注釋，我可能說的不清楚

解釋一下二分查找：

可以看到我的代碼里面新建了一個數組cpynums1復制nums1，然后對其排序，將nums2中的元素作為目標值，找出目標值在cpynums1的插入的位置，那就可以找出那個最小值啦。

貼上代碼：

int compare(const void *a,const void *b)
//qsort函數，升序排序
{
    return *(int *)a-*(int *)b;
}
int binarySearch(int *arr,int len,int target)
//二分查找：得到的是target插入的一個位置的下標，在返回值的左邊，也就是我返回的是target的右邊界
{
    int left=0;
    int right=len-1;
    int mid;
    while(left<right)
    {
        mid=(right-left)/2+left;
        //防止rightright+left太大越出int的范圍
        if(arr[mid]<=target) left=mid+1;
        //如果target比中間值大（有可能等于中間值），這時候應該要移動左邊界
        //當target等于中間值的時候，為什么要讓left=mid+1呢？
        //因為我要我的返回值是右邊屆，因此應該跳過target==[mid]的mid值，取其右邊界
        else right=mid;
        //否則就移動右邊界到mid中，此時有可能是left==right，就可以返回右邊界了
    }
    return left;
    //返回的是右邊界的下標
}
int SearchMax(int *arr,int len)
//直接查找：nums1[i]-nums2[i])-abs(nums1[min]-nums2[i]的最大值其所對應的下標
{
    int maxnum=arr[0];
    int maxindex=0;
    for(int i=1;i<len;i++)
    {
        if(maxnum<arr[i])
        {
            maxnum=arr[i];
            maxindex=i;
        }
    }
    return maxindex;
}
const int mod=1000000007;//對結果取余mod
int minAbsoluteSumDiff(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
    int cpynums1[nums1Size];
    //創建一個nums1Size的數組，準備復制nums1
    memcpy(cpynums1,nums1,nums1Size*sizeof(int));
    //復制nums1
    qsort(cpynums1,nums1Size,sizeof(int),compare);
    //將復制nums1的數組cpynums1升序排列
    int maxdiff_arr[nums1Size];
    //創建一個數組，用來存對應nums2每一個元素的abs(nums1[i]-nums2[i])-abs(nums1[min]-nums2[i]
    for(int i=0;i<nums1Size;i++)
    {
        int right_index=binarySearch(cpynums1,nums1Size,nums2[i]);
        //得到nums2[i]在cpynums1中插入位置的右邊界坐標
        right_index==0?right_index=1:right_index;
        //如果右坐標為0的時候，應該讓其等于1，否則下面就越界
        int min_diff=fmin(abs(nums2[i]-cpynums1[right_index]),abs(nums2[i]-cpynums1[right_index-1]));
        //這里的abs(nums1[min]-nums2[i])應該取nums2[i]與兩邊界的最小值
        maxdiff_arr[i]=abs(nums1[i]-nums2[i])-min_diff;
        //存進數組：abs(nums1[i]-nums2[i])-abs(nums1[min]-nums2[i])
    }
    int maxNum_index=SearchMax(maxdiff_arr,nums1Size);
    //求出abs(nums1[i]-nums2[i])-abs(nums1[min]-nums2[i])所對應的下標
    long sum=0;
    //最終的返回計算結果，別忘了取余
    for(int i = 0;i<nums1Size;i++)
    {
        if(i!=maxNum_index) sum+=abs(nums1[i]-nums2[i]);
        else sum+=abs(nums1[i]-nums2[i])-maxdiff_arr[maxNum_index];
        //如果到了所對應的下標，那就根據63行的算式：maxdiff_arr[i]=abs(nums1[i]-nums2[i])-min_diff，加上替換元素后的差值
    }
    return sum%mod;
}

性能分析： 時間復雜度：

在一個循環里面使用了二分查找，因此時間復雜度是：

O(n)*O(logn)=O(nlogn)

空間復雜度：

這題其實是用空間換時間，新建了兩個數組，用來存中間值

因此空間復雜度是：

O(n)

粗暴做法（超時）

int compare(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int findmaxIndex(int *array,int len)
{
    int temp=array[0];
    int maxIndex=0;
    for(int i=1;i<len;i++)
    {
        if(temp<array[i]) 
        {
            temp=array[i];
            maxIndex=i;
        }
    }
    return maxIndex;
}
const int mod=1000000007;
int minAbsoluteSumDiff(int* nums1, int nums1Size, int* nums2, int nums2Size){
    //qsort(nums1,nums1Size,sizeof(int),compare);//排序
    //qsort(nums2,nums2Size,sizeof(int),compare);//排序
    int *arr1=(int *)malloc(sizeof(int)*nums1Size);//nums1[j]-nums2[i]的最佳結果：最小值
    int *arr2=(int *)malloc(sizeof(int)*nums1Size);//存num1[i]-nums2[i] - abs(nums1[j]-nums2[i])
    for(int i=0;i<nums1Size;i++)
    {
        arr1[i]=100000;
        for(int j=0;j<nums1Size;j++)
        {
            arr1[i]=fmin(arr1[i],abs(nums1[j]-nums2[i]));
        }
        arr2[i]=abs(abs(nums1[i]-nums2[i])-arr1[i]);
    }
    int m_index=findmaxIndex(arr2,nums1Size);
    int sum=0;
    for(int i=0;i<nums1Size;i++)
    {
        if(i!=m_index) sum+=abs(nums1[i]-nums2[i]);
        else sum+=arr1[m_index];
    }
    free(arr1);
    free(arr2);
    return sum%mod;
}