题目描述

给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2，每个数组中的元素 互不相同，请你返回 最小 的数字，两个数组都 至少 包含这个数字的某个数位。

样例

输入：nums1 = [4,1,3], nums2 = [5,7]
输出：15
解释：数字 15 的数位 1 在 nums1 中出现，数位 5 在 nums2 中出现。15 是我们能得到的最小数字。

输入：nums1 = [3,5,2,6], nums2 = [3,1,7]
输出：3
解释：数字 3 的数位 3 在两个数组中都出现了。

限制

• 1 <= nums1.length, nums2.length <= 9
• 1 <= nums1[i], nums2[i] <= 9
• 每个数组中，元素 互不相同。

算法

(思维题) $O(n + m)$

1. 如果两个数组存在相同的数字，则最小相同数字就是答案。
2. 否则，分别找到两个数组中最小的数字，然后这两个数字较小的作为十位，较大的作为个位。

时间复杂度

• 使用哈希表存储其中一个数组，在另一个数组中寻找相同的数字，时间复杂度为 $O(n + m)$。
• 接着遍历两个数组各一次。
• 故总时间复杂度为 $O(n + m)$。

空间复杂度

• 需要 $O(\min(n, m))$ 的额外空间存储其中一个数组的哈希表。

C++ 代码

class Solution {
public:
    int minNumber(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s1(nums1.begin(), nums1.end());

        int ans = 10;
        for (int x : nums2)
            if (s1.find(x) != s1.end())
                ans = min(ans, x);

        if (ans < 10)
            return ans;

        int m1 = 10, m2 = 10;
        for (int x : nums1)
            m1 = min(m1, x);

        for (int x : nums2)
            m2 = min(m2, x);

        return min(m1, m2) * 10 + max(m1, m2);
    }
};