LC.P88[合并两个有序数组]

方法一：模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] ans = new int[m + n];
        for (int index = 0, i = 0, j = 0; index < m + n; ++index) {
            if (i < m && j < n) {
                ans[index] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];
            } else if (i < m) {
                ans[index] = nums1[i++];
            } else if (j < n) {
                ans[index] = nums2[j++];
            }
        }
        if (m + n >= 0) System.arraycopy(ans, 0, nums1, 0, m + n);
    }
}
  • 时间复杂度：$O(m + n)$
  • 空间复杂度：$O(m + n)$

方法二：双指针

1
2
3
4
5
6
7
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m - 1, j = n - 1, k = m + n - 1; j >= 0; --k) {
            nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
        }
    }
}
  • 时间复杂度：$O(m + n)$
  • 空间复杂度：$O()$