前言:剑指offer刷题系列
问题:
给你两个只包含 1 到 9 之间数字的数组 nums1
和 nums2
,每个数组中的元素 互不相同 ,请你返回 最小 的数字,两个数组都 至少 包含这个数字的某个数位。
示例:
输入:nums1 = [4,1,3], nums2 = [5,7]
输出:15
解释:数字 15 的数位 1 在 nums1 中出现,数位 5 在 nums2 中出现。15 是我们能得到的最小数字。
思路:
这道题要找到一个最小数字,数字中的每一位都存在于两个数组中。通过示例可以知道有两种情况:
两个数组中存在相同的数,那么最小数字肯定是这个相同的数。如果存在多个相同的数,那取相同数中的最小值。【换句话说,如果两个数组有交集,最小数字就是交集的最小值】
两个数组中不存在相同的数,那么最小数字肯定是一个两位数,由两个数组各自的最小值组成。并且十位一定小于个位,保证结果最小。
首先,将输入的两个整数列表nums1
和nums2
转换为集合(set),这样可以去除列表中的重复元素,确保后续操作不会重复计算相同的数字。
接下来,计算两个集合nums1
和nums2
的交集,也就是它们共同包含的元素。这个交集存储在变量intersection
中。
这里使用条件判断检查交集是否为空。如果交集不为空,说明两个列表中至少有一个共同的元素。
如果交集不为空,直接返回交集中的最小元素。因为我们的目标是使整数尽可能小,所以应该选择交集中的最小元素。
如果交集为空,意味着两个列表没有共同的元素,此时需要分别找到两个列表中的最小元素:
min_num1 = min(nums1)
:找到集合nums1
中的最小元素。min_num2 = min(nums2)
:找到集合nums2
中的最小元素。
最后,根据两个最小元素,构建一个整数。这个整数由两个最小元素按顺序组成,首先是较小的最小元素乘以10,然后加上较大的最小元素。这样构造的整数尽可能小,因为将较小的最小元素放在前面,符合数字的规则。
基于上述思考,代码如下:
class Solution:
def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
nums1= set(nums1)
nums2 = set(nums2)
intersection = nums1 & nums2
if intersection:
return min(intersection)
min_num1 = min(nums1)
min_num2 = min(nums2)
return 10 * min(min_num1, min_num2) + max(min_num1, min_num2)
执行结果如下图:
学到的知识点:
- 集合的交集操作: 使用
&
运算符计算两个集合的交集。这对于找出两个集合中共同存在的元素非常有用。 - 整数的构建和拼接: 代码演示了如何构建一个整数,将两个整数按照一定规则拼接在一起。这对于处理数字数据和字符串拼接非常有用。