88. Merge Sorted Array

解法一

思路

直接使用 System.arraycopy() 函数后 sort。

代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n); // nums2: 要 copy 的数组; 0: 开始 copy 的位置; nums1: copy in 数组; m: copy in 的位置; n: copy 的个数
        Arrays.sort(nums1);
    }
}

时间复杂度 O((n+m)log(m+n))，因为自己进行了一次排序。

解法一

思路

利用 sorted array 这个条件。
在两个数组最后一个有效值处放置指针 （n-1 和 m-1）并且在 nums1 的末尾放置指针 n + m -1
如果两个数组指针都还没到头
把 nums1的末尾和 nums2 的末尾值较大的那个放到数组的末尾。数组末尾指针前移，较大数所在数组指针前移。
如果 nums1 指针到头而 nums2 的还没到头
把剩余的 nums2 元素放进 nums1 中
如果 nums2 到头而 nums1 还没到头
无需进行任何操作因为 nums1 已经排序过了

代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int l1 = m - 1;
        int l2 = n - 1;
        int last  = n + m - 1;
        while (l1 >= 0 && l2 >= 0) {
            if (nums1[l1] >= nums2[l2]) {
                nums1[last] = nums1[l1];
                l1--;
            }
            else {
                nums1[last] = nums2[l2];
                l2--;
            }
            last--;
        }

        while (l2 >= 0) {
            nums1[last--] = nums2[l2--];
        }
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接