您的位置:首页 > 科技 > 能源 > LeetCode-day36-3132. 找出与数组相加的整数 II

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

2024/12/23 8:26:32 来源:https://blog.csdn.net/weixin_43344005/article/details/141065435  浏览:    关键词:LeetCode-day36-3132. 找出与数组相加的整数 II

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

  • 题目描述
  • 示例
    • 示例1:
    • 示例2:
  • 思路
  • 代码

题目描述

给你两个整数数组 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 相等。

思路

排序+判断子序列

例如排序后 nums1 = [2,5,6,7,8,10], nums2 =[3,4,5,8],如果 nums1 中保留下来的最小元素是 nums1[1] = 5,那么 x=nums2[0]−nums1[1]=3−5=−2,这意味着如果我们把 nums1 的每个数都加上 x=−2,得到 nums1=[0,3,4,5,6,8],问题就变成判断 nums2是否为 nums1的子序列,如果是子序列,那么我们就可以放心地移除多余的两个数了。

代码

class Solution:def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:nums1.sort()nums2.sort()for i in range(2,0,-1):x = nums2[0] - nums1[i]j = 0for v in nums1[i:]:if nums2[j] == v + x:j +=1if j == len(nums2):return xreturn nums2[0] - nums1[0]

版权声明:

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

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