Description#
Given two arrays of unique digits nums1 and nums2, return the smallest number that contains at least one digit from each array.
Example 1:
Input: nums1 = [4,1,3], nums2 = [5,7]
Output: 15
Explanation: The number 15 contains the digit 1 from nums1 and the digit 5 from nums2. It can be proven that 15 is the smallest number we can have.
Example 2:
Input: nums1 = [3,5,2,6], nums2 = [3,1,7]
Output: 3
Explanation: The number 3 contains the digit 3 which exists in both arrays.
Constraints:
1 <= nums1.length, nums2.length <= 91 <= nums1[i], nums2[i] <= 9- All digits in each array are unique.
Solutions#
Solution 1: Enumeration#
We observe that if there are the same numbers in the arrays $nums1$ and $nums2$, then the minimum of the same numbers is the smallest number. Otherwise, we take the number $a$ in the array $nums1$ and the number $b$ in the array $nums2$, and concatenate the two numbers $a$ and $b$ into two numbers, and take the smaller number.
The time complexity is $O(m \times n)$, and the space complexity is $O(1)$, where $m$ and $n$ are the lengths of the arrays $nums1$ and $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
}
}
|
Solution 2: Hash Table or Array + Enumeration#
We can use a hash table or array to record the numbers in the arrays $nums1$ and $nums2$, and then enumerate $1 \sim 9$. If $i$ appears in both arrays, then $i$ is the smallest number. Otherwise, we take the number $a$ in the array $nums1$ and the number $b$ in the array $nums2$, and concatenate the two numbers $a$ and $b$ into two numbers, and take the smaller number.
The time complexity is $(m + n)$, and the space complexity is $O(C)$. Where $m$ and $n$ are the lengths of the arrays $nums1$ and $nums2$ respectively; and $C$ is the range of the numbers in the arrays $nums1$ and $nums2$, and the range in this problem is $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)
}
}
|
Solution 3: Bit Operation#
Since the range of the numbers is $1 \sim 9$, we can use a binary number with a length of $10$ to represent the numbers in the arrays $nums1$ and $nums2$. We use $mask1$ to represent the numbers in the array $nums1$, and use $mask2$ to represent the numbers in the array $nums2$.
If the number $mask$ obtained by performing a bitwise AND operation on $mask1$ and $mask2$ is not equal to $0$, then we extract the position of the last $1$ in the number $mask$, which is the smallest number.
Otherwise, we extract the position of the last $1$ in $mask1$ and $mask2$ respectively, and denote them as $a$ and $b$, respectively. Then the smallest number is $min(a \times 10 + b, b \times 10 + a)$.
The time complexity is $O(m + n)$, and the space complexity is $O(1)$. Where $m$ and $n$ are the lengths of the arrays $nums1$ and $nums2$ respectively.
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);
}
|
