当前位置: 首页> 游戏> 游戏 > 【leetcode】找出与数组相加的整数II( 过程反思 思路详解 )

【leetcode】找出与数组相加的整数II( 过程反思 思路详解 )

时间:2025/7/10 18:11:49来源:https://blog.csdn.net/H13420972436/article/details/141066277 浏览次数:0次

 

题目分析:

         题目要咱们除掉nums1中的两个数,从另一个角度理解就是找到nums1中与nums2元素匹配的nums1.size() - 2个数

        由题目可知,二者元素具有相差 x 的一一对应关系,如此,不难想到应首先通过对二者排序来构建大致的匹配格局。

int miimumAddedInteger(vector<int>& nums1, vector<int>& nums2){sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());
}

接着就是遍历和计算:

错误示范:

x 一定可以由 nums1的最大的4个数 和 nums2最大的两个数确定。。。吗?

一开始笔者希望通过上述原理找到 x, 但最终宣告无解

比如测试数据, 应该删掉 7, 10,并得出x = 1

但是如果用两个数组最大的几个数来确定,就会得出x=0

nums1 = [0, 1, 2, 4, 5, 7, 8, 9, 10]
nums2 = [1, 2, 3, 5, 8, 9, 10]

而且!

推而广之,无论用最大的多少个数确定,只要将nums1填充元素,前面数字按照 x=1 填充d,后面数字按 x=0 填充,就不能保证成功确定 x

反过来,将上面的情况应用于两个数组最小的那些数,依然不成功

总的来说!不能通过局部来确定x,x必须要经过x全体人民(元素)的检验!

 正解:双指针

//AC后参考大佬解法优化了下过程

关于 for(int i=0; i<3; i++)  的简单说明:

        因为删除元素只有两个,那么,一定可以通过nums2的最小元素和nums1的前三个元素算出正确x,再将其交给全体人民检验哈哈哈

class Solution {
public:int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {int s1 = nums1.size();int s2 = s1-2;sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());  int x, minix = INT_MAX;                for(int i=0; i<3; i++){x = nums2[0] - nums1[i];  int id1 = i, id2 = 0;while(id1 < s1 && id2 < s2){if(nums1[id1] + x == nums2[id2]) id2++;id1++;}if(id2 == s2) minix = min(minix, x);			}return minix;}
};

~希望对你有启发~ 

关键字:【leetcode】找出与数组相加的整数II( 过程反思 思路详解 )

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: