LeetCode --- 字符串、数组
简书专栏：https://www.jianshu.com/nb/41796568
知乎专栏：https://zhuanlan.zhihu.com/c_174823416
一、题目描述
来源：力扣（LeetCode）
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
要求实现函数：
public void merge(int[] nums1, int m, int[] nums2, int n) {}
二、实现思路以及代码
- 因为两个数组都是有序数组，且nums1数组空间足够大，我们考虑定义两个指针p,q指向nums1,nums2，分别从后向前遍历
- 定义指针len = m+n -1 表示最终数组的最后一位
- 依次比较出大的元素，从后向前放
- 若nums1先遍历完，则表明nums2中剩余元素均小于nums1元素，直接填充到最前面即可；若nums2先遍历完成，则nums1就不需要变动了，即为结果
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int p = m - 1;
int q = n - 1;
int len = m + n - 1;
while (p >= 0 && q >= 0) {
nums1[len--] = (nums1[p] > nums2[q] ? nums1[p--] : nums2[q--]);
}
//如果q小于0，那么就已经有序了，如果p小于0，就把nums2剩余部分插入到最开始部分
if (p < 0) {
System.arraycopy(nums2, 0, nums1, 0, q + 1);
}
}
三、测试代码
public static void main(String[] args) {
int[] nums1 = {1,2,4,0,0,0,0,0,0,0};
int[] nums2 = {3,5};
merge(nums1,3,nums2,2);
System.out.println(Arrays.toString(nums1));
}
输出结果为：
[1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
