2605-从两个数字数组里生成最小数字

给你两个只包含 1 到 9 之间数字的数组 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 <= 9
• 1 <= nums1[i], nums2[i] <= 9
• 每个数组中，元素 互不相同 。

方法一：分类讨论

思路与算法

如果 nums}_1 和 nums}_2 中有相同的数字，那么我们选出其中最小的那个即为答案，它是一个一位数。这一步可以使用哈希表解决：将 nums}_1 中的所有数字放入一个哈希集合，再依次枚举 nums}_2 中的每个数字，判断其是否在哈希集合中即可。

如果 nums}_1 和 nums}_2 中没有相同的数字，那么取 nums}_1 最小的数字 x 和 nums}_2 中最小的数字 y，组成一个两位数，即为答案。答案是 \overline{xy 和 \overline{yx 中的较小值。

代码

[sol1-C++]

class Solution {
public:
    int minNumber(vector<int>& nums1, vector<int>& nums2) {
        auto same = [&]() -> int {
            unordered_set<int> s(nums1.begin(), nums1.end());
            int x = 10;
            for (int num: nums2) {
                if (s.count(num)) {
                    x = min(x, num);
                }
            }
            return x == 10 ? -1 : x;
        };

        if (int x = same(); x != -1) {
            return x;
        }
        
        int x = *min_element(nums1.begin(), nums1.end());
        int y = *min_element(nums2.begin(), nums2.end());
        return min(x * 10 + y, y * 10 + x);
    }
};

[sol1-Java]

class Solution {
    public int minNumber(int[] nums1, int[] nums2) {
        int s = same(nums1, nums2);
        if (s != -1) {
            return s;
        }
        
        int x = Arrays.stream(nums1).min().getAsInt();
        int y = Arrays.stream(nums2).min().getAsInt();
        return Math.min(x * 10 + y, y * 10 + x);
    }

    public int same(int[] nums1, int[] nums2) {
        Set<Integer> s = new HashSet<Integer>();
        for (int num : nums1) {
            s.add(num);
        }
        int x = 10;
        for (int num : nums2) {
            if (s.contains(num)) {
                x = Math.min(x, num);
            }
        }
        return x == 10 ? -1 : x;
    }
}

[sol1-C#]

public class Solution {
    public int MinNumber(int[] nums1, int[] nums2) {
        int s = Same(nums1, nums2);
        if (s != -1) {
            return s;
        }
        
        int x = nums1.Min();
        int y = nums2.Min();
        return Math.Min(x * 10 + y, y * 10 + x);
    }

    public int Same(int[] nums1, int[] nums2) {
        ISet<int> s = new HashSet<int>();
        foreach (int num in nums1) {
            s.Add(num);
        }
        int x = 10;
        foreach (int num in nums2) {
            if (s.Contains(num)) {
                x = Math.Min(x, num);
            }
        }
        return x == 10 ? -1 : x;
    }
}

[sol1-Python3]

class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        def same() -> int:
            s = set(nums1) & set(nums2)
            return -1 if not s else min(s)
        
        if (x := same()) != -1:
            return x
        
        x = min(nums1)
        y = min(nums2)
        return min(x * 10 + y, y * 10 + x)

[sol1-C]

typedef struct {
    int key;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, int key) {
    HashItem *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, int key) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    HASH_ADD_INT(*obj, key, pEntry);
    return true;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr);
    }
}

int same(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    HashItem *set = NULL;
    for (int i = 0; i < nums1Size; i++) {
        hashAddItem(&set, nums1[i]);
    }
    int x = 10;
    for (int i = 0; i < nums2Size; i++) {
        if (hashFindItem(&set, nums2[i])) {
            x = fmin(x, nums2[i]);
        }
    }
    hashFree(&set);
    return x == 10 ? -1 : x;
}

int minNumber(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int count = same(nums1, nums1Size, nums2, nums2Size);
    if (count != -1) {
        return count;
    }
    int x = INT_MAX, y = INT_MAX;
    for (int i = 0; i < nums1Size; i++) {
        x = fmin(x, nums1[i]);
    }
    for (int i = 0; i < nums2Size; i++) {
        y = fmin(y, nums2[i]);
    }
    return fmin(x * 10 + y, y * 10 + x);
}       

[sol1-Go]

func minNumber(nums1 []int, nums2 []int) int {
    var same = func() int {
        s := make(map[int]bool)
        x := 10
        for _, num := range nums1 {
            s[num] = true
        }
        for _, num := range nums2 {
            if _, ok := s[num]; ok {
                x = min(x, num)
            }
        }
        if x == 10 {
            return -1
        }
        return x
    }

    if x := same(); x != -1 {
        return x;
    }
    x, y := nums1[0], nums2[0]
    for _, num := range nums1 {
        x = min(x, num)
    }
    for _, num := range nums2 {
        y = min(y, num)
    }
    return min(x * 10 + y, y * 10 + x)
}

func min(x int, y int) int {
    if x > y {
        return y
    }
    return x
}

[sol1-JavaScript]

var minNumber = function(nums1, nums2) {
    const same = () => {
        const s = new Set(nums1);
        let x = 10;
        for (const m of nums2) {
            if (s.has(m)) {
                x = Math.min(x, m);
            }
        }
        return x == 10 ? -1 : x;
    }
    const count = same();
    if (count != -1) {
        return count;
    }
    const x = Math.min(...nums1);
    const y = Math.min(...nums2);
    return Math.min(x * 10 + y, y * 10 + x);
};

复杂度分析

• 时间复杂度：O(m + n)，其中 m 和 n 分别是数组 nums}_1 和 nums}_2 的长度。

• 空间复杂度：O(m)，即为哈希表需要使用的空间。