题目描述：
给你两个只包含 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 <= 91 <= 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)
