2024年2月15日发(作者：山君豪)
【华为OD机试真题JAVA】数组按规则合并问题 题目及解析
题目：
有两个有序数组A和B，长度分别为n和m，需要将它们合并为一个有序数组C并去重，其中规则如下：
1. 如果A[i]和B[j]相同，则只保留一个。
2. 如果A[i]和B[j]不相同，则将较小的数插入到C中，同时i和j指针都向后移动一位，直到其中一个指针到达末尾为止。
3. 如果A还有剩余，则将剩余元素全部插入到C中； 如果B还有剩余，则将剩余元素全部插入到C中。
要求：时间复杂度O(n+m)，空间复杂度O(1)。
解析：
该问题在数据结构和算法中经常被用到，其解法主要有双指针法和归并排序。这里介绍一种基于双指针的解法。
首先，定义三个指针：i、j和k，分别指向数组A、数组B和数组C的当前最小元素。然后，根据规则比较A[i]和B[j]的大小，将较小的数插入到C[k]中，并将对应指针向后移动一个位置，直到其中一个指针到达末尾为止，即A[i]或B[j]到了数组的最后一个元素。
最后，将剩余元素全部插入到C中，即如果A还有元素没处理，则将A中的所有元素插入到C中；如果B还有元素没处理，则将B中的所有元素插入到C中。
代码实现如下：
public static int[] merge(int[] nums1, int[] nums2) {
int n1 = , n2 = , k = 0;
int[] nums = new int[n1 + n2];
int i = 0, j = 0;
while (i < n1 && j < n2) {
if (nums1[i] == nums2[j]) {
nums[k++] = nums1[i];
i++;
j++;
} else if (nums1[i] < nums2[j]) {
nums[k++] = nums1[i];
i++;
} else {
nums[k++] = nums2[j];
j++;
}
}
while (i < n1) {
nums[k++] = nums1[i++];
}
while (j < n2) {
nums[k++] = nums2[j++];
}
return (nums, k);
}
时间复杂度分析：
双指针遍历两个数组的时间复杂度为O(n+m)，空间复杂度为O(1)。最后将结果拷贝到新的数组中的时间复杂度为O(k)，其中k为结果数组的长度，即去重后的元素个数。因此，总时间复杂度为O(n+m+k)。
2024年2月15日发(作者：山君豪)
【华为OD机试真题JAVA】数组按规则合并问题 题目及解析
题目：
有两个有序数组A和B，长度分别为n和m，需要将它们合并为一个有序数组C并去重，其中规则如下：
1. 如果A[i]和B[j]相同，则只保留一个。
2. 如果A[i]和B[j]不相同，则将较小的数插入到C中，同时i和j指针都向后移动一位，直到其中一个指针到达末尾为止。
3. 如果A还有剩余，则将剩余元素全部插入到C中； 如果B还有剩余，则将剩余元素全部插入到C中。
要求：时间复杂度O(n+m)，空间复杂度O(1)。
解析：
该问题在数据结构和算法中经常被用到，其解法主要有双指针法和归并排序。这里介绍一种基于双指针的解法。
首先，定义三个指针：i、j和k，分别指向数组A、数组B和数组C的当前最小元素。然后，根据规则比较A[i]和B[j]的大小，将较小的数插入到C[k]中，并将对应指针向后移动一个位置，直到其中一个指针到达末尾为止，即A[i]或B[j]到了数组的最后一个元素。
最后，将剩余元素全部插入到C中，即如果A还有元素没处理，则将A中的所有元素插入到C中；如果B还有元素没处理，则将B中的所有元素插入到C中。
代码实现如下：
public static int[] merge(int[] nums1, int[] nums2) {
int n1 = , n2 = , k = 0;
int[] nums = new int[n1 + n2];
int i = 0, j = 0;
while (i < n1 && j < n2) {
if (nums1[i] == nums2[j]) {
nums[k++] = nums1[i];
i++;
j++;
} else if (nums1[i] < nums2[j]) {
nums[k++] = nums1[i];
i++;
} else {
nums[k++] = nums2[j];
j++;
}
}
while (i < n1) {
nums[k++] = nums1[i++];
}
while (j < n2) {
nums[k++] = nums2[j++];
}
return (nums, k);
}
时间复杂度分析：
双指针遍历两个数组的时间复杂度为O(n+m)，空间复杂度为O(1)。最后将结果拷贝到新的数组中的时间复杂度为O(k)，其中k为结果数组的长度，即去重后的元素个数。因此，总时间复杂度为O(n+m+k)。