题目

88. 合并两个有序数组【简单】

题解

双指针

归并排序思想解决，类似的题还有21. 合并两个有序链表

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3=new int[m+n];
        int i=0,j=0,number=0;
        while(i<m&&j<n){
            if(nums1[i]<nums2[j]){
                nums3[number++]=nums1[i++];
            }
            else{
                nums3[number++]=nums2[j++];
            }
        }
        //复制剩余元素到nums3
        while(i<m){
            nums3[number++]=nums1[i++];
        }
        while(j<n){
            nums3[number++]=nums2[j++];
        }
        for(int k=0;k<m+n;k++){
            nums1[k]=nums3[k];
        }
    }
}

时间复杂度： $O (m + n)$
空间复杂度： $O (m + n)$

逆向双指针

$n u m s 1$ 的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进 $n u m s 1$ 的最后面。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=m-1,j=n-1,number=m+n-1;
        while(i>=0||j>=0){
            //nums1为空
            if(i<0){
                nums1[number--]=nums2[j--];
                continue;
            }
            //nums2为空
            if(j<0){
                nums1[number--]=nums1[i--];
                continue;
            }
            //逆序双指针
            if(nums1[i]>nums2[j]){
                nums1[number--]=nums1[i--];
            }
            else{
                nums1[number--]=nums2[j--];
            }
        }
    }
}