LeetCode百题【合并两个有序数组】

题目描述

题目描述.png

解法一

简单粗暴，俩数组一拼再排序

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2,0,nums1,m,n);
        Arrays.sort(nums1);
    }
}

复杂度分析

时间复杂度：O((m+n)log(m+n)) —-Arrays.sort方法对int默认的排序方法为快排
空间复杂度：O(log(m+n))

解法二

双指针

//与官方解法类似 不过是倒着来的
// 倒序遍历两个数组，将大的数从后往前插入nums1，并将指针向前移动一位，直至其中一个数组遍历完，将另一个未遍历完的数组全部插入到nums1
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;//左指针->nums1
        int j = n - 1;//右指针->nums2
        int k = nums1.length - 1;
        while (i >= 0 && j >= 0){
            nums1[k--]=nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
        }//两个数组都没遍历完时的处理
        
        //其中一个数组遍历完了，进行单个处理，否则会下标越界
        while(i>=0){
            nums1[k--]=nums1[i--];
        }
        while(j>=0){
            nums1[k--]=nums2[j--];
        }
    }
}