88. 合并两个有序数组-双指针(易)

题目描述

链接:https://leetcode-cn.com/problems/merge-sorted-array/submissions/
给定两个有序整数数组 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]

解题思路

首先想到使用暴力算法, 但是会存在一个问题: 当把第二个数组插入到第一个数组的适当位置时, 需要把数组1的某一个范围的数整体向右移动一位, 腾出空间.

另外一种方法: 直接从右向左使用双指针i,j
因为是有序, 只需要每次比较把最大的放到合适的位置(结果数组Num1的尾部)即可.
最后只有一种可能性: num2剩余, 而num1没有剩余. 处理即可.
(因为num1前面的都是已经排好序的, 如果num2没有剩余, 就说明num1之前的那些数都比num2小, 而num1整体又排好序, 所以就不用动).

复杂度分析

T: O(m+n)
S: O(1)

代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1, j = n-1, k = nums1.length-1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] >= nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        // 只需要把Num2剩余的数组拷贝回即可
        while (j >= 0) nums1[k--] = nums2[j--];
    }
}