绝对差值的和
问题分析:
-
取模操作的位置不正确:
- 你在计算
result - max_
之前没有正确处理大数取模,这可能导致数值溢出。
- 你在计算
-
最大差值减少量的计算:
- 算法中的内部循环效率较低,可以优化。
优化后的代码:
我们可以参考官方题解,优化算法并确保取模操作的正确性。
class Solution {
public:
int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
int length_ = nums1.size();
long result = 0;
long max_ = 0;
// 先计算初始的绝对差值和
for (int i = 0; i < length_; i++) {
result += abs(nums1[i] - nums2[i]);
}
// 找到可以替换的最大差值减少量
vector<int> sorted_nums1 = nums1;
sort(sorted_nums1.begin(), sorted_nums1.end());
for (int i = 0; i < length_; i++) {
int original_diff = abs(nums1[i] - nums2[i]);
auto it = lower_bound(sorted_nums1.begin(), sorted_nums1.end(), nums2[i]);
int new_diff = original_diff;
if (it != sorted_nums1.end()) {
new_diff = min(new_diff, abs(*it - nums2[i]));
}
if (it != sorted_nums1.begin()) {
new_diff = min(new_diff, abs(*prev(it) - nums2[i]));
}
max_ = max(max_, original_diff - new_diff);
}
return (int)((result - max_) % 1000000007);
}
};
详细解释优化后的代码:
-
计算初始绝对差值和:
for (int i = 0; i < length_; i++) { result += abs(nums1[i] - nums2[i]); }
- 首先计算
nums1
和nums2
每个对应元素的绝对差值的和。
- 首先计算
-
对
nums1
进行排序:vector<int> sorted_nums1 = nums1; sort(sorted_nums1.begin(), sorted_nums1.end());
- 为了更高效地找到可以替换的元素,我们对
nums1
进行排序。
- 为了更高效地找到可以替换的元素,我们对
-
遍历每个元素并尝试找到最佳替换:
for (int i = 0; i < length_; i++) { int original_diff = abs(nums1[i] - nums2[i]); auto it = lower_bound(sorted_nums1.begin(), sorted_nums1.end(), nums2[i]); int new_diff = original_diff; if (it != sorted_nums1.end()) { new_diff = min(new_diff, abs(*it - nums2[i])); } if (it != sorted_nums1.begin()) { new_diff = min(new_diff, abs(*prev(it) - nums2[i])); } max_ = max(max_, original_diff - new_diff); }
- 对于每个
nums2[i]
,使用二分查找在排序后的nums1
中找到最接近的元素,并计算替换后的新差值。 - 更新最大差值减少量
max_
。
- 对于每个
-
计算最终结果并取模:
return (int)((result - max_) %