LeetCode 2605 从两个数字数组里生成最小数字
探寻两个数组数位关联下的最小数字问题
题目描述
给定两个只包含 1 到 9 之间数字的数组 nums1
和 nums2
,并且每个数组中的元素都是互不相同的。我们需要返回最小的数字,要求这个数字满足两个数组都至少包含这个数字的某个数位。例如,若 nums1 = [4, 1, 3]
,nums2 = [5, 7]
,那么满足条件的最小数字就是通过相应规则计算出来的某个值(后续会详细讲解如何得出)。
解题思路
为了解决这个问题,我们可以分情况来思考并处理:
情况一:存在交集数字
首先尝试找出两个数组中共同出现的数字,也就是它们的交集部分。我们可以通过双层循环遍历两个数组,对每一个 nums1
中的元素,去和 nums2
中的所有元素进行比较。一旦发现有相同的数字,记录下来,并持续更新找到的最小的交集数字。若最终能找到交集数字,那么这个最小的交集数字必然就是我们要找的结果,因为它天然满足两个数组都包含其某个数位,而且在所有交集数字里是最小的,自然也就是符合要求的最小数字了。
情况二:不存在交集数字
要是经过前面的查找,发现两个数组没有共同的数字,那我们就分别找出 nums1
和 nums2
数组各自的最小数字,分别记为 min1
和 min2
。接着,把这两个最小数字组合成两个不同顺序的两位数,具体来说,让 min1
作为十位数字、min2
作为个位数字组成一个数字 num1
,反过来,让 min2
作为十位数字、min1
作为个位数字组成另一个数字 num2
。最后返回这两个数字中较小的那个,它就是在没有交集数字情况下满足题目条件的最小数字了。
代码实现
#include <stdio.h>
#include <stdlib.h>
// 核心函数,用于找出满足条件的最小数字
int minNumber(int* nums1, int nums1Size, int* nums2, int nums2Size) {
// 用于记录是否存在交集数字以及交集中最小的数字,初始化为较大值方便比较更新
int minIntersection = 10;
// 标记是否存在交集,初始化为0表示不存在
int hasIntersection = 0;
// 寻找两个数组的交集数字,并确定交集中最小的数字
for (int i = 0; i < nums1Size; ++i) {
for (int j = 0; j < nums2Size; ++j) {
if (nums1[i] == nums2[j]) {
hasIntersection = 1;
if (nums1[i] < minIntersection) {
minIntersection = nums1[i];
}
}
}
}
// 如果存在交集,直接返回交集中最小的数字
if (hasIntersection) {
return minIntersection;
}
// 分别找出nums1和nums2数组中的最小数字
int min1 = 10, min2 = 10;
for (int i = 0; i < nums1Size; ++i) {
if (nums1[i] < min1) {
min1 = nums1[i];
}
}
for (int i = 0; i < nums2Size; ++i) {
if (nums2[i] < min2) {
min2 = nums2[i];
}
}
// 组成两种顺序的数字并返回较小的那个
int num1 = min1 * 10 + min2;
int num2 = min2 * 10 + min1;
return num1 < num2? num1 : num2;
}
// 测试函数,用于执行多个测试用例并展示结果
void testMinNumber() {
// 测试用例 1
int nums1_1[] = {4, 1, 3};
int nums1Size_1 = sizeof(nums1_1) / sizeof(nums1_1[0]);
int nums2_1[] = {5, 7};
int nums2Size_1 = sizeof(nums2_1) / sizeof(nums2_1[0]);
int result_1 = minNumber(nums1_1, nums1Size_1, nums2_1, nums2Size_1);
printf("测试用例 1: nums1 = {4, 1, 3}, nums2 = {5, 7}, 结果: %d\n", result_1);
// 测试用例 2
int nums1_2[] = {1, 2, 3};
int nums1Size_2 = sizeof(nums1_2) / sizeof(nums1_2[0]);
int nums2_2[] = {4, 5, 6};
int nums2Size_2 = sizeof(nums2_2) / sizeof(nums2_2[0]);
int result_2 = minNumber(nums1_2, nums1Size_2, nums2_2, nums2Size_2);
printf("测试用例 2: nums1 = {1, 2, 3}, nums2 = {4, 5, 6}, 结果: %d\n", result_2);
// 测试用例 3
int nums1_3[] = {2, 8};
int nums1Size_3 = sizeof(nums1_3) / sizeof(nums1_3[0]);
int nums2_3[] = {7, 9};
int nums2Size_3 = sizeof(nums2_3) / sizeof(nums2_3[0]);
int result_3 = minNumber(nums1_3, nums1Size_3, nums2_3, nums2Size_3);
printf("测试用例 3: nums1 = {2, 8}, nums2 = {7, 9}, 结果: %d\n", result_3);
// 测试用例 4(存在交集情况)
int nums1_4[] = {1, 5, 9};
int nums1Size_4 = sizeof(nums1_4) / sizeof(nums1_4[0]);
int nums2_4[] = {5, 8, 2};
int nums2Size_4 = sizeof(nums2_4) / sizeof(nums2_4[0]);
int result_4 = minNumber(nums1_4, nums1Size_4, nums2_4, nums2Size_4);
printf("测试用例 4: nums1 = {1, 5, 9}, nums2 = {5, 8, 2}, 结果: %d\n", result_4);
}
int main() {
testMinNumber();
return 0;
}
寻找交集部分
在 minNumber
函数里,一开始我们定义了两个重要的变量:minIntersection
初始化为 10
(由于题目中数字范围是 1
到 9
,这个初始值方便后续比较更新找到交集中最小数字),以及 hasIntersection
并初始化为 0
,用于标记是否存在交集情况。
然后通过两层嵌套的 for
循环来遍历数组 nums1
和 nums2
,当 nums1
中的某个元素和 nums2
中的某个元素相等时,意味着找到了交集数字,此时把 hasIntersection
置为 1
表示存在交集,并且把当前相同的数字与 minIntersection
比较,如果当前数字更小,就更新 minIntersection
的值。
根据交集情况处理
如果经过前面的循环,hasIntersection
的值变为了 1
,那就说明存在交集数字,这种情况下,我们直接返回 minIntersection
,因为这个数字就是满足两个数组都包含其某个数位的最小数字了。
无交集时的处理
要是 hasIntersection
仍然是 0
,也就是不存在交集,那我们就要分别找出数组 nums1
和 nums2
中的最小数字了。定义 min1
和 min2
并都初始化为 10
,同样利用 for
循环遍历各自的数组,在循环过程中不断更新 min1
和 min2
为各自数组中的最小数字
得到两个最小数字后,按照之前说的思路,将它们组成两个不同顺序的两位数,也就是 num1
(min1
作为十位、min2
作为个位)和 num2
(min2
作为十位、min1
作为个位),最后通过三目运算符 return num1 < num2? num1 : num2;
返回这两个数字中较小的那个,而这个较小数字就是在没有交集数字的情况下,满足题目条件的最小数字了。
在 testMinNumber
函数中,我们定义了多个不同情况的测试用例,分别调用 minNumber
函数并输出相应的结果,方便直观地验证函数在不同输入情况下的正确性。
希望通过这篇博客,大家对这道有趣的编程题目有更深入的理解,并且能掌握相应的解题思路与代码实现方法。如果有任何疑问或者建议,欢迎在评论区留言交流呀!
上述代码中,minNumber
函数实现了核心的查找最小数字逻辑,而 testMinNumber
函数用于进行多组测试用例的验证,在 main
函数中调用 testMinNumber
函数来展示不同情况的测试结果,整体上可以更好地帮助理解整个解题过程以及代码的功能。你可以根据实际需要进一步拓展测试用例或者对代码进行优化调整等操作哦。