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
每个数组中，元素 互不相同 。

解法一：哈希表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func minNumber(nums1 []int, nums2 []int) int {
    record := make(map[int]bool)
    for _, nums := range nums1 {
        record[nums] = true
    }
    sort.Ints(nums2)
    for _, nums := range nums2 {
        if record[nums] {
            return nums
        }
    }
    sort.Ints(nums1)
    a, b := nums1[0], nums2[0]
    if a > b {
        a, b = b, a
    }
    return a*10 + b
}

解法二：位运算

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


func countTrailingZeros(num int) int {
    count := 0
    for num != 0 && num&1 == 0 {
        count++
        num >>= 1
    }
    return count
}
func minNumber(nums1 []int, nums2 []int) int {
    recordA, recordB := 0, 0
    for _, num := range nums1 {
        recordA |= 1 << num
    }
    for _, num := range nums2 {
        recordB |= 1 << num
    }
    if recordA&recordB != 0 {
        return countTrailingZeros(recordA & recordB)
    } else {
        a, b := countTrailingZeros(recordA), countTrailingZeros(recordB)
        if a > b {
            a, b = b, a
        }
        return a*10 + b
    }
}