88.合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/

难度 简单

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明：

• 初始化 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]

提示：

• -10^9 <= nums1[i], nums2[i] <= 10^9
• nums1.length == m + n
• nums2.length == n

---

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1]

Constraints:

0 <= n, m <= 200
1 <= n + m <= 200
nums1.length == m + n
nums2.length == n
-109 <= nums1[i], nums2[i] <= 109

思路

• 从右向左扫描，避免从左向右扫描出现的覆盖数组中已有值的问题
• p1_left 与 p2 指向值中取较大的，值放到 p1_right 位置上去

• p1_right 左移
  • 如果第一步中，较大的是 p1_left，那么 p1_left 左移 1 位；如果较大的是 p2 那么 p2 左移 1 位

• 退出条件1：当 nums2 全部放入 nums1 中时，就可以退出了，即 p2 < 0

• 退出条件2：当 p1_left 移动到 -1 时，将 nums2 的 [0, p2] 范围内的元素复制到 nums1 对应位置中

public class _88合并两个有序数组 {

public static void merge(int[] nums1, int m, int[] nums2, int n) {

int p1_left = m - 1;

int p1_right = m + n - 1;

int p2 = n - 1;

while (p2 >= 0) {

if (p1_left >= 0 && nums1[p1_left] > nums2[p2]) // 正常情况

nums1[p1_right--] = nums1[p1_left--];

else // 情况1：p1_left 已经从左边跑出去了，那么将 nums2 [0, p2] 范围的值复制到 Num1 对应位置

nums1[p1_right--] = nums2[p2--]; // 情况2：nums2当前位置的值较大，把它从nums2复制到Nums1去

// 两种情况的代码恰好一致

}

}

public static void main(String[] args) {

int[] nums1 = {1, 2, 3, 0, 0, 0};

int[] nums2 = {2, 5, 6};

merge(nums1, 3, nums2, 3);

for (int i : nums1) {

System.out.print(i + " ");

}

}

}