跳转至

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

解法

方法一：枚举

我们观察发现，如果数组 \(nums1\) 和 \(nums2\) 中有相同的数字，那么相同数字中的最小值一定是最小的数字。否则我们取 \(nums1\) 中的数字 \(a\) 和 \(nums2\) 中的数字 \(b\)，将 \(a\) 和 \(b\) 拼接成两个数字，取其中较小的数字即可。

时间复杂度 \(O(m \times n)\)，空间复杂度 \(O(1)\)。其中 \(m\) 和 \(n\) 分别是数组 \(nums1\) 和 \(nums2\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int minNumber(int[] nums1, int[] nums2) {
        int ans = 100;
        for (int a : nums1) {
            for (int b : nums2) {
                if (a == b) {
                    ans = Math.min(ans, a);
                } else {
                    ans = Math.min(ans, Math.min(a * 10 + b, b * 10 + a));
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int minNumber(vector<int>& nums1, vector<int>& nums2) {
        int ans = 100;
        for (int a : nums1) {
            for (int b : nums2) {
                if (a == b) {
                    ans = min(ans, a);
                } else {
                    ans = min({ans, a * 10 + b, b * 10 + a});
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func minNumber(nums1 []int, nums2 []int) int {
    ans := 100
    for _, a := range nums1 {
        for _, b := range nums2 {
            if a == b {
                ans = min(ans, a)
            } else {
                ans = min(ans, min(a*10+b, b*10+a))
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function minNumber(nums1: number[], nums2: number[]): number {
    let ans = 100;
    for (const a of nums1) {
        for (const b of nums2) {
            if (a === b) {
                ans = Math.min(ans, a);
            } else {
                ans = Math.min(ans, a * 10 + b, b * 10 + a);
            }
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn min_number(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let mut ans = 100;

        for &a in &nums1 {
            for &b in &nums2 {
                if a == b {
                    ans = std::cmp::min(ans, a);
                } else {
                    ans = std::cmp::min(ans, std::cmp::min(a * 10 + b, b * 10 + a));
                }
            }
        }

        ans
    }
}

方法二：哈希表或数组 + 枚举

我们可以用哈希表或数组记录数组 \(nums1\) 和 \(nums2\) 中的数字，然后枚举 \(1 \sim 9\)，如果 \(i\) 在两个数组中都出现了，那么 \(i\) 就是最小的数字。否则我们取 \(nums1\) 中的数字 \(a\) 和 \(nums2\) 中的数字 \(b\)，将 \(a\) 和 \(b\) 拼接成两个数字，取其中较小的数字即可。

时间复杂度 \((m + n)\)，空间复杂度 \(O(C)\)。其中 \(m\) 和 \(n\) 分别是数组 \(nums1\) 和 \(nums2\) 的长度；而 \(C\) 是数组 \(nums1\) 和 \(nums2\) 中数字的范围，本题中 \(C = 10\)。

1
2
3
4
5
6
7
class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        s = set(nums1) & set(nums2)
        if s:
            return min(s)
        a, b = min(nums1), min(nums2)
        return min(a * 10 + b, b * 10 + a)

 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
class Solution {
    public int minNumber(int[] nums1, int[] nums2) {
        boolean[] s1 = new boolean[10];
        boolean[] s2 = new boolean[10];
        for (int x : nums1) {
            s1[x] = true;
        }
        for (int x : nums2) {
            s2[x] = true;
        }
        int a = 0, b = 0;
        for (int i = 1; i < 10; ++i) {
            if (s1[i] && s2[i]) {
                return i;
            }
            if (a == 0 && s1[i]) {
                a = i;
            }
            if (b == 0 && s2[i]) {
                b = i;
            }
        }
        return Math.min(a * 10 + b, b * 10 + a);
    }
}

 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
class Solution {
public:
    int minNumber(vector<int>& nums1, vector<int>& nums2) {
        bitset<10> s1;
        bitset<10> s2;
        for (int x : nums1) {
            s1[x] = 1;
        }
        for (int x : nums2) {
            s2[x] = 1;
        }
        int a = 0, b = 0;
        for (int i = 1; i < 10; ++i) {
            if (s1[i] && s2[i]) {
                return i;
            }
            if (!a && s1[i]) {
                a = i;
            }
            if (!b && s2[i]) {
                b = i;
            }
        }
        return min(a * 10 + b, b * 10 + a);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func minNumber(nums1 []int, nums2 []int) int {
    s1 := [10]bool{}
    s2 := [10]bool{}
    for _, x := range nums1 {
        s1[x] = true
    }
    for _, x := range nums2 {
        s2[x] = true
    }
    a, b := 0, 0
    for i := 1; i < 10; i++ {
        if s1[i] && s2[i] {
            return i
        }
        if a == 0 && s1[i] {
            a = i
        }
        if b == 0 && s2[i] {
            b = i
        }
    }
    return min(a*10+b, b*10+a)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function minNumber(nums1: number[], nums2: number[]): number {
    const s1: boolean[] = new Array(10).fill(false);
    const s2: boolean[] = new Array(10).fill(false);
    for (const x of nums1) {
        s1[x] = true;
    }
    for (const x of nums2) {
        s2[x] = true;
    }
    let a = 0;
    let b = 0;
    for (let i = 1; i < 10; ++i) {
        if (s1[i] && s2[i]) {
            return i;
        }
        if (a === 0 && s1[i]) {
            a = i;
        }
        if (b === 0 && s2[i]) {
            b = i;
        }
    }
    return Math.min(a * 10 + b, b * 10 + a);
}

 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
27
28
29
30
31
32
33
34
use std::collections::HashMap;

impl Solution {
    pub fn min_number(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let mut h1: HashMap<i32, bool> = HashMap::new();

        for &n in &nums1 {
            h1.insert(n, true);
        }

        let mut h2: HashMap<i32, bool> = HashMap::new();
        for &n in &nums2 {
            h2.insert(n, true);
        }

        let mut a = 0;
        let mut b = 0;
        for i in 1..10 {
            if h1.contains_key(&i) && h2.contains_key(&i) {
                return i;
            }

            if a == 0 && h1.contains_key(&i) {
                a = i;
            }

            if b == 0 && h2.contains_key(&i) {
                b = i;
            }
        }

        std::cmp::min(a * 10 + b, b * 10 + a)
    }
}

方法三：位运算

由于数字的范围是 \(1 \sim 9\)，我们可以用一个长度为 \(10\) 的二进制数来表示数组 \(nums1\) 和 \(nums2\) 中的数字。我们用 \(mask1\) 表示数组 \(nums1\) 中的数字，用 \(mask2\) 表示数组 \(nums2\) 中的数字。

如果 \(mask1\) 和 \(mask2\) 进行按位与得到的数字 \(mask\) 不等于 \(0\)，那么我们提取 \(mask\) 中最后一位 \(1\) 所在的位置，即为最小的数字。

否则，我们分别提取 \(mask1\) 和 \(mask2\) 中最后一位 \(1\) 所在的位置，分别记为 \(a\) 和 \(b\)，那么最小的数字就是 \(min(a \times 10 + b, b \times 10 + a)\)。

时间复杂度 \(O(m + n)\)，空间复杂度 \(O(1)\)。其中 \(m\) 和 \(n\) 分别是数组 \(nums1\) 和 \(nums2\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        mask1 = mask2 = 0
        for x in nums1:
            mask1 |= 1 << x
        for x in nums2:
            mask2 |= 1 << x
        mask = mask1 & mask2
        if mask:
            return (mask & -mask).bit_length() - 1
        a = (mask1 & -mask1).bit_length() - 1
        b = (mask2 & -mask2).bit_length() - 1
        return min(a * 10 + b, b * 10 + a)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minNumber(int[] nums1, int[] nums2) {
        int mask1 = 0, mask2 = 0;
        for (int x : nums1) {
            mask1 |= 1 << x;
        }
        for (int x : nums2) {
            mask2 |= 1 << x;
        }
        int mask = mask1 & mask2;
        if (mask != 0) {
            return Integer.numberOfTrailingZeros(mask);
        }
        int a = Integer.numberOfTrailingZeros(mask1);
        int b = Integer.numberOfTrailingZeros(mask2);
        return Math.min(a * 10 + b, b * 10 + a);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minNumber(vector<int>& nums1, vector<int>& nums2) {
        int mask1 = 0, mask2 = 0;
        for (int x : nums1) {
            mask1 |= 1 << x;
        }
        for (int x : nums2) {
            mask2 |= 1 << x;
        }
        int mask = mask1 & mask2;
        if (mask) {
            return __builtin_ctz(mask);
        }
        int a = __builtin_ctz(mask1);
        int b = __builtin_ctz(mask2);
        return min(a * 10 + b, b * 10 + a);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func minNumber(nums1 []int, nums2 []int) int {
    var mask1, mask2 uint
    for _, x := range nums1 {
        mask1 |= 1 << x
    }
    for _, x := range nums2 {
        mask2 |= 1 << x
    }
    if mask := mask1 & mask2; mask != 0 {
        return bits.TrailingZeros(mask)
    }
    a, b := bits.TrailingZeros(mask1), bits.TrailingZeros(mask2)
    return min(a*10+b, b*10+a)
}

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function minNumber(nums1: number[], nums2: number[]): number {
    let mask1: number = 0;
    let mask2: number = 0;
    for (const x of nums1) {
        mask1 |= 1 << x;
    }
    for (const x of nums2) {
        mask2 |= 1 << x;
    }
    const mask = mask1 & mask2;
    if (mask !== 0) {
        return numberOfTrailingZeros(mask);
    }
    const a = numberOfTrailingZeros(mask1);
    const b = numberOfTrailingZeros(mask2);
    return Math.min(a * 10 + b, b * 10 + a);
}

function numberOfTrailingZeros(i: number): number {
    let y = 0;
    if (i === 0) {
        return 32;
    }
    let n = 31;
    y = i << 16;
    if (y != 0) {
        n = n - 16;
        i = y;
    }
    y = i << 8;
    if (y != 0) {
        n = n - 8;
        i = y;
    }
    y = i << 4;
    if (y != 0) {
        n = n - 4;
        i = y;
    }
    y = i << 2;
    if (y != 0) {
        n = n - 2;
        i = y;
    }
    return n - ((i << 1) >>> 31);
}

评论