题目描述
给你两个整数数组 nums1
和 nums2
。
从 nums1
中移除两个元素,并且所有其他元素都与变量 x
所表示的整数相加。如果 x
为负数,则表现为元素值的减少。
执行上述操作后,nums1
和 nums2
相等 。当两个数组中包含相同的整数,并且这些整数出现的频次相同时,两个数组 相等。
返回能够实现数组相等的 最小 整数 x
。
样例
输入:nums1 = [4,20,16,12,8], nums2 = [14,18,10]
输出:-2
解释:
移除 nums1 中下标为 [0,4] 的两个元素,并且每个元素与 -2 相加后,nums1 变为 [18,14,10],
与 nums2 相等。
输入:nums1 = [3,5,5,3], nums2 = [7,7]
输出:2
解释:
移除 nums1 中下标为 [0,3] 的两个元素,并且每个元素与 2 相加后,nums1 变为 [7,7],
与 nums2 相等。
限制
3 <= nums1.length <= 200
nums2.length == nums1.length - 2
0 <= nums1[i], nums2[i] <= 1000
- 测试用例以这样的方式生成:存在一个整数
x
,nums1
中的每个元素都与x
相加后,再移除两个元素,nums1
可以与nums2
相等。
算法
(思维题) $O(n \log n)$
- 分别对两个数组从小到大排序。
- 排序后,答案
x
尽可能来源三个差值:nums2[0] - nums1[2]
,nums2[0] - nums1[1]
或nums2[0] - nums1[0]
,即nums1
的前三个元素中的一个与nums2
作差。 - 对于每个
x
,通过双指针遍历判定两个数组是否匹配。
时间复杂度
- 排序的时间复杂度为 $O(n \log n)$。
- 每次判定的时间复杂度为 $O(n)$。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(\log n)$ 的额外空间存储排序的系统栈。
C++ 代码
class Solution {
public:
int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
const int n = nums2.size();
auto check = [&](int x) {
for (int i = 0, j = 0; j < n; j++) {
while (i < n + 2 && nums1[i] + x < nums2[j])
++i;
if (i == n + 2 || nums1[i] + x != nums2[j])
return false;
++i;
}
return true;
};
if (check(nums2[0] - nums1[2]))
return nums2[0] - nums1[2];
if (check(nums2[0] - nums1[1]))
return nums2[0] - nums1[1];
return nums2[0] - nums1[0];
}
};