欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 汽车 > 新车 > LeetCode.3132.找出与数组相加的整数II

LeetCode.3132.找出与数组相加的整数II

2024/11/30 14:35:47 来源:https://blog.csdn.net/ALLe_Y/article/details/141073003  浏览:    关键词:LeetCode.3132.找出与数组相加的整数II

题目描述:
 

给你两个整数数组 nums1 和 nums2

从 nums1 中移除两个元素,并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数,则表现为元素值的减少。

执行上述操作后,nums1 和 nums2 相等 。当两个数组中包含相同的整数,并且这些整数出现的频次相同时,两个数组 相等 。

返回能够实现数组相等的 最小 整数 x 

输入输出实例:

思路:我们先对两个列表元素进行排序,这样更便于我们找到x,题目中要求我们在nums1中删除两个元素后都加x才能与nums2匹配,那么我们可以确定,我们在nums1中找三个元素,那么这三个元素肯定至少有一个是满足不被删除的,既然它不用被删除,那他与nums2中对应元素相减得到的就可能是我们的x。为了方便我们可以选用前三个元素,也就是nums1[2],nums1[1],nums1[0]中至少有一个满足条件,这里我们遍历的时候从高往低遍历,因为题目要我们找最小的x(如果nums1=[1,2,3],nums2=[4],用这个例子可以直观的看出来我们的x是4-3=1),这三个元素中肯定有一个对应的是nums2[0],所以nums2[0]-nums1[i]一定有一个是我们的x。然后我们用双指针,第一个指针n1起始位置在nums1[i+1],第二个指针n2起始位置在nums2[1],然后我们找n2所指的元素减去n1所指的元素和nums2[0]-nums1[i]比,如果不同,那么我们第一个指针往右走,如果相同我们两个指针都往右走,直到有一个指针走完列表,如果最后第二个指针走到了最后,那么说明这个时候的nums2[0]-nums1[i]就是我们要找的x。(如果觉得还是有点难以理解,可以跟着上诉思路对着实例自己画图做一做,会清晰很多)根据上述思路有以下代码:

class Solution:def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:#对nums1和nums2两个列表进行排序nums1.sort()nums2.sort()m,n = len(nums1),len(nums2)#既然要移除两个元素,那么我们找nums1三个元素,这三个元素里面肯定至少有一个是被保留的#我们可以找前三个或者是后三个,需要注意的是题目要我们找最小的整数x,为了保证最小,我们找的三个元素顺序是从大往小遍历for i in [2,1,0]:#采用双指针,从i+1,1开始是因为我们要用第i(nums1),0(nums2)这些元素用来做找到x的标准n1,n2 = i+1,1while n1 < m and n2 < n :#判断第i个是否满足被保留if nums2[0] - nums1[i] == nums2[n2] - nums1[n1]:n2 += 1n1 += 1#n2=n的时候我们找完if n2 == n :return nums2[0] - nums1[i]

 

版权声明:

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

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