1. 题目来源
链接:1818. 绝对差值和
2. 题目解析
二分题目,中等意思。
首先,贪心思路的大失败…一开始想的是找到绝对值差最大的数对,将其替换成最小即可。错误样例 [1,28,21] [9,21,20] 9 ,贪心思路是万万行不通的…貌似周赛比赛时贪心竟然能过…后来重判了。
反正就是对 nums2[i] 找到在 nums1 中最近接的它的数,每次看看能否更新最优解即可,找的过程是
O
(
l
o
g
n
)
O(logn)
O(logn),
n
n
n 次查找就是
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。
二分 nums1 ,并找到第一个大于等于 nums[i] 数的位置,最接近它的就是该数与它前面的一个数,常用技巧了。
在定义全局答案的时候,手误写了 1e9 ,以为是极大值了…结果被大数据卡掉了…犯病了啊。
时间复杂度:
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 空间复杂度:
O
(
n
)
O(n)
O(n)
class Solution {
public:
const int MOD = 1e9+7;
typedef long long LL;
int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> q = nums1;
sort(q.begin(), q.end());
LL res = 0;
for (int i = 0; i < n; i ++ ) res += abs(nums1[i] - nums2[i]);
LL ans = 1e18;
for (int i = 0; i < n; i ++ ) {
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (q[mid] < nums2[i]) l = mid + 1;
else r = mid;
}
ans = min(ans, res - abs(nums1[i] - nums2[i]) + abs(q[l] - nums2[i]));
if (l > 0) ans = min(ans, res - abs(nums1[i] - nums2[i]) + abs(q[l - 1] - nums2[i]));
}
return ans % MOD;
}
};
|