在线做qq空间的网站,网页设计与网站建设简答题,广州做网站厉害的公司,vue 做企业网站【LetMeFly】3132.找出与数组相加的整数 II#xff1a;排序3次尝试(nlog n)
力扣题目链接#xff1a;https://leetcode.cn/problems/find-the-integer-added-to-array-ii/
给你两个整数数组 nums1 和 nums2。
从 nums1 中移除两个元素#xff0c;并且所有其他元素都与变量…【LetMeFly】3132.找出与数组相加的整数 II排序3次尝试(nlog n)
力扣题目链接https://leetcode.cn/problems/find-the-integer-added-to-array-ii/
给你两个整数数组 nums1 和 nums2。
从 nums1 中移除两个元素并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数则表现为元素值的减少。
执行上述操作后nums1 和 nums2 相等 。当两个数组中包含相同的整数并且这些整数出现的频次相同时两个数组 相等 。
返回能够实现数组相等的 最小 整数 x 。 示例 1: 输入nums1 [4,20,16,12,8], nums2 [14,18,10] 输出-2
解释
移除 nums1 中下标为 [0,4] 的两个元素并且每个元素与 -2 相加后nums1 变为 [18,14,10] 与 nums2 相等。
示例 2: 输入nums1 [3,5,5,3], nums2 [7,7] 输出2
解释
移除 nums1 中下标为 [0,3] 的两个元素并且每个元素与 2 相加后nums1 变为 [7,7] 与 nums2 相等。 提示
3 nums1.length 200nums2.length nums1.length - 20 nums1[i], nums2[i] 1000测试用例以这样的方式生成存在一个整数 xnums1 中的每个元素都与 x 相加后再移除两个元素nums1 可以与 nums2 相等。
解题方法排序3次尝试
分别对两个数组排序。因为一定有解所以nums1中前3个元素至少有一个和nums2[0]对应。也就是说可能的x最多有3种情况。对于每种情况我们从大到小尝试如果当前x可行则返回。
怎么判定nums1删除两个元素后是否每个元素加上x后都和nums2对应呢只需要两个指针分别指向两个数组中的元素。 在指针没有超出数组有效范围时 若 n u m s 1 [ n 1 ] x n u m s 2 [ n 2 ] nums1[n1] x nums2[n2] nums1[n1]xnums2[n2]则两个指针分别后移否则跳过nums1中的这个数n1后移n2不动“跳过次数”加一。若跳过次数大于2则说明这个x不可行 最终如果n2指到nums2的末尾则说明这个x可行。 时间复杂度 O ( n log n ) O(n\log n) O(nlogn)空间复杂度 O ( log n ) O(\log n) O(logn)
AC代码
C
class Solution {
private:bool isOk(vectorint nums1, vectorint nums2, int x) {int skip 0;int n1 0, n2 0;while (n1 nums1.size() n2 nums2.size()) {if (nums1[n1] x nums2[n2]) {n1, n2;}else {n1, skip;if (skip 2) {return false;}}}return n2 nums2.size();}
public:int minimumAddedInteger(vectorint nums1, vectorint nums2) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());for (int i 2; i 0; i--) {if (isOk(nums1, nums2, nums2[0] - nums1[i])) {return nums2[0] - nums1[i];}}return -1; // Fake Return}
};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/141072842
