LeetCode 题解工作台
从两个数字数组里生成最小数字
给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2 ，每个数组中的元素 互不相同 ，请你返回 最小 的数字，两个数组都 至少 包含这个数字的某个数位。 示例 1： 输入： nums1 = [4,1,3], nums2 = [5,7] 输出： 15 解释： 数字 15 的数位 1 …
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们观察发现，如果数组 和 中有相同的数字，那么相同数字中的最小值一定是最小的数字。否则我们取 中的数字 和 中的数字 ，将 和 拼接成两个数字，取其中较小的数字即可。 时间复杂度 $O(m \times n)$，空间复杂度 。其中 和 分别是数组 和 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
nums1 和 nums2 ，每个数组中的元素 互不相同 ，请你返回 最小 的数字，两个数组都 至少 包含这个数字的某个数位。
示例 1：
输入：nums1 = [4,1,3], nums2 = [5,7] 输出：15 解释：数字 15 的数位 1 在 nums1 中出现，数位 5 在 nums2 中出现。15 是我们能得到的最小数字。
示例 2：
输入：nums1 = [3,5,2,6], nums2 = [3,1,7] 输出：3 解释：数字 3 的数位 3 在两个数组中都出现了。
提示：
1 <= nums1.length, nums2.length <= 91 <= nums1[i], nums2[i] <= 9- 每个数组中，元素 互不相同 。
解题思路
方法一：枚举
我们观察发现，如果数组 和 中有相同的数字，那么相同数字中的最小值一定是最小的数字。否则我们取 中的数字 和 中的数字 ，将 和 拼接成两个数字，取其中较小的数字即可。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 和 的长度。
class Solution:
def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
ans = 100
for a in nums1:
for b in nums2:
if a == b:
ans = min(ans, a)
else:
ans = min(ans, 10 * a + b, 10 * b + a)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests the candidate's ability to efficiently scan and compare arrays.
- question_mark
Evaluates understanding of hash tables for fast lookups.
- question_mark
Checks the ability to handle edge cases like no common digits.
常见陷阱
外企场景- error
Failing to handle the case where no common digits exist.
- error
Incorrectly assuming arrays are always guaranteed to have common digits.
- error
Not optimizing the solution with hash table lookups, resulting in slower solutions.
进阶变体
外企场景- arrow_right_alt
What if the arrays contain more than one common digit? (Handle multiple common digits)
- arrow_right_alt
What if the arrays contain non-digit elements? (Handle invalid inputs)
- arrow_right_alt
What if the input arrays have a larger length limit? (Scale the solution accordingly)