b_lc_绝对差值和(贪心)

可以选用 A 中的 任意一个 元素来替换 A 中的 至多 一个元素,以 最小化 绝对差值和(|A[i] - B[i]|)。
在替换数组 A 中最多一个元素 之后 ,返回最小绝对差值和(n<=1e5)

贪心:每次找到最接近 B[i] 的数 (小于B[i]以及>=B[i],结果个数可能是0或1或2个),然后取每次替换后的增量,看看谁小。

const int mod=1e9+7;
class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& A, vector<int>& B) {
        int d = 0, n = A.size();
        for (int i=0; i<n; i++) {
            d = (d + abs(A[i]-B[i])) % mod;
        }
        set<int> st(A.begin(), A.end());
        int ans = INT_MAX;
        for (int i=0; i<n; i++) {
            auto it = st.lower_bound(B[i]);
            if (it != st.end()) { //先找>=B[i]先判断这个可以减少一次it++运算
                int v = *it;
                int t = d - abs(A[i] - B[i]) + abs(v - B[i]);
                ans = min(ans, t);
            }
            if (it != st.begin()) { //再找<B[i]的
                it--;
                int v = *it;
                int t = d - abs(A[i] - B[i]) + abs(v - B[i]);
                ans = min(ans, t);
            }
        }
        return ans;
    }
};
上一篇:LC 234. 回文链表


下一篇:LC 146. LRU 缓存机制