题目描述:
给你两个只包含 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 中有相同的元素,则这两个相同的元素都可以构成这个数字的各位,那么这个数字就是一个 1 – 9 之间的个位数,则找出所有相同的元素中的最小值,结果就是这个最小的相同元素。我们可以将一个数组中的所有元素添加到一个哈希集合中,在遍历第二个数组,判断其中的每个元素是否在哈希集合存在,取最小值即可。
-
如果 nums1 和 nums2 没有相同的元素,那么分别取两个数组中的最小值 x 和 y,答案为 (x * 10 + y) 和 (y * 10 + x) 的最小值。
代码实现:
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);
}
private 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;
}
}
复杂度分析:
时间复杂度: O(m + n),其中 m 和 n 分别是数组 nums1 和 nums2 的长度。
空间复杂度: O(m),m 为哈希集合所需要的空间。
解法二:位运算
算法思路:
由于题目中两个数组中的数字范围都是 1 – 9,那么我们可以用一个长度为 10 的二进制数来表示数字中的元素。假设使用 mask1 来表示 nums1 中的数字,使用 mask2 来表示 nums2 中的数字。将 mask1 和 mask2 按位与后得到 mask,会有以下两种结果:
如果 mask 不为 0,则说明两个数组中有相同数字,取相同数字的最小值即为答案。那么我们取 mask 中最后一位 1 所在位置后面的 0 的位数,就是最小的数字。
如果 mask 为 0,那么分别取 mask1 和 mask2 中最后一位 1 所在位置后面的0的位数,最小的数字为 min(a * 10 + b, b * 10 + a)。
代码实现:
class Solution {
public int minNumber(int[] nums1, int[] nums2) {
int mask1 = 0, mask2 = 0;
// 将数组中的元素用二进制位中的1表示
for( int num : nums1){
mask1 |= 1 << num;
}
for( int num : nums2){
mask2 |= 1 << num;
}
// 如果mask不为0则表示有相同元素
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);
}
}
Integer.numberOfTrailingZeros() 是 Java 中的一个静态方法,它的作用是计算一个整数的二进制表示中从最低位开始连续的0的个数。
复杂度分析:
时间复杂度: O(m + n),其中 m 和 n 分别是数组 nums1 和 nums2 的长度。
空间复杂度: O(1)