1818. 絕對內插補點和-每日一題

一、題目

  給你兩個正整數數組 nums1 和 nums2 ，數組的長度都是 n 。

  數組 nums1 和 nums2 的 絕對內插補點和 定義為所有 |nums1[i] - nums2[i]|（0 <= i < n）的 總和（下标從 0 開始）。

  你可以選用 nums1 中的 任意一個 元素來替換 nums1 中的 至多 一個元素，以 最小化 絕對內插補點和。

  在替換數組 nums1 中最多一個元素 之後 ，傳回最小絕對內插補點和。因為答案可能很大，是以需要對 109 + 7 取餘 後傳回。

|x| 定義為：

• 如果 x >= 0 ，值為 x ，或者
• 如果 x <= 0 ，值為 -x

點選檢視原題

難度級别：中等

二、思路

1）TreeSet

  善于使用已有的資料結構可以快速解題，本題很容易誤解用貪心可以很好地求解，但存在以下情況，當兩個數組分别為

{5, 5, 5, 4}

和

{10, 8, 7, 6}

時，無法使用貪心求解，隻能根據

nums2

的每個元素

nums2[i]

，找在

nums1

中最貼近

nums2[i]

的數字，再與原來的內插補點做對比，找到減少最小絕對內插補點的最大值，記錄下來

三、代碼

1）TreeSet

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        long ans = 0;
        TreeSet<Integer> ts = new TreeSet();
        for (int i = 0; i < nums1.length; i++) {
            ts.add(nums1[i]);
            ans += Math.abs(nums1[i] - nums2[i]);	// 将最小絕對內插補點進行累加
        }
        int pre = 0;
        for (int i = 0; i < nums1.length; i++) {
            int temp = Math.abs(nums1[i] - nums2[i]);
            Integer floor = ts.floor(nums2[i]);		// 找到小于等于nums2[i]的數
            Integer ceiling = ts.ceiling(nums2[i]);	// 找到大于等于nums2[i]的數
            int newMargin = ((floor == null)? Integer.MAX_VALUE : (nums2[i] - floor));
            newMargin = Math.min(newMargin, ((ceiling == null)? newMargin : (ceiling - nums2[i])));
            pre = Math.max(pre, Math.abs(temp - newMargin));	// 記錄改變絕對內插補點的最大改變量
        }
        return (int)((ans - pre)%1000000007);
    }
}
           

  時間複雜度為

O(nlogn)

，空間複雜度為

O(n)

，但由于每次循環都有兩次尋找

nums1

中的數，這部分可以自己寫二分查找來實作一次查找，找到兩個數