Easy

题目描述

给定两个由不同数字组成的数组 nums1 和 nums2，返回包含每个数组中至少一个数字的最小数字。

示例 1：

输入：nums1 = [4,1,3], nums2 = [5,7]
输出：15
解释：数字 15 包含来自 nums1 的数字 1 和来自 nums2 的数字 5。可以证明 15 是我们可以拥有的最小数字。

示例 2：

输入：nums1 = [3,5,2,6], nums2 = [3,1,7]
输出：3
解释：数字 3 包含数字 3，该数字存在于两个数组中。

约束条件：

  • 1 <= nums1.length, nums2.length <= 9
  • 1 <= nums1[i], nums2[i] <= 9
  • 每个数组中的所有数字都是唯一的。

提示：

  • 结果数字最多有多少位？
  • 结果数字将有一位或两位数字。尝试找出每种情况何时可能。

解题思路

这道题要求我们找到包含两个数组中至少各一个数字的最小数字。

解题思路：

  1. 情况一：存在公共数字 - 如果两个数组有公共数字，那么答案就是最小的公共数字，因为单个数字一定比两位数字小。

  2. 情况二：不存在公共数字 - 如果没有公共数字，我们需要组成一个两位数。为了让数字最小，我们应该让十位数尽可能小，个位数也尽可能小。

具体实现：

  • 首先找出两个数组的交集中的最小值
  • 如果存在交集，直接返回最小公共数字
  • 如果不存在交集，分别找出两个数组的最小值，然后比较 min1*10 + min2 和 min2*10 + min1 的大小，返回较小值

时间复杂度优化： 由于数组长度最大为9且元素范围是1-9，我们可以用数组或集合来快速查找交集。

代码实现

class Solution {
public:
    int minNumber(vector<int>& nums1, vector<int>& nums2) {
        // 使用集合找交集
        unordered_set<int> set1(nums1.begin(), nums1.end());
        int commonMin = 10; // 初始化为不可能的值
        
        for (int num : nums2) {
            if (set1.count(num)) {
                commonMin = min(commonMin, num);
            }
        }
        
        // 如果有公共数字，返回最小的公共数字
        if (commonMin != 10) {
            return commonMin;
        }
        
        // 没有公共数字，组成两位数
        int min1 = *min_element(nums1.begin(), nums1.end());
        int min2 = *min_element(nums2.begin(), nums2.end());
        
        return min(min1 * 10 + min2, min2 * 10 + min1);
    }
};

class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        # 找交集中的最小值
        common = set(nums1) & set(nums2)
        if common:
            return min(common)
        
        # 没有公共数字，组成两位数
        min1, min2 = min(nums1), min(nums2)
        return min(min1 * 10 + min2, min2 * 10 + min1)

public class Solution {
    public int MinNumber(int[] nums1, int[] nums2) {
        // 使用HashSet找交集
        var set1 = new HashSet<int>(nums1);
        int commonMin = 10; // 初始化为不可能的值
        
        foreach (int num in nums2) {
            if (set1.Contains(num)) {
                commonMin = Math.Min(commonMin, num);
            }
        }
        
        // 如果有公共数字，返回最小的公共数字
        if (commonMin != 10) {
            return commonMin;
        }
        
        // 没有公共数字，组成两位数
        int min1 = nums1.Min();
        int min2 = nums2.Min();
        
        return Math.Min(min1 * 10 + min2, min2 * 10 + min1);
    }
}

var minNumber = function(nums1, nums2) {
    // 找交集中的最小值
    const set1 = new Set(nums1);
    let commonMin = 10; // 初始化为不可能的值
    
    for (const num of nums2) {
        if (set1.has(num)) {
            commonMin = Math.min(commonMin, num);
        }
    }
    
    // 如果有公共数字，返回最小的公共数字
    if (commonMin !== 10) {
        return commonMin;
    }
    
    // 没有公共数字，组成两位数
    const min1 = Math.min(...nums1);
    const min2 = Math.min(...nums2);
    
    return Math.min(min1 * 10 + min2, min2 * 10 + min1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m + n)m 和 n 分别是两个数组的长度，需要遍历数组找交集和最小值
空间复杂度O(min(m, n))使用集合存储较小数组的元素用于查找交集