Leetcode Algorithms-88.Merge Sorted Array

问题地址

Merge Sorted Array - LeetCode

问题描述

0.jpg

解法1

正向迭代,此时需要顾虑nums1的长度变化情况,因此比较臃肿。

1
public class Solution {
2
3
    public void merge(int[] nums1, int m, int[] nums2, int n) {
4
        int i1 = 0;
5
        int lengthI1 = m; 
6
        int orginI1 = 0;
7
        int i2 = 0;
8
        while (orginI1 < m && i2 < n) {
9
            if (nums2[i2] >= nums1[i1]) orginI1++;
10
            else {
11
                this.insert(nums2[i2], nums1, lengthI1, i1);
12
                lengthI1++;
13
                i2++;
14
            }
15
            i1++;
16
        }
17
        if (orginI1 == m)
18
            for (int i = i2; i < n; i++) nums1[i1++] = nums2[i];
19
    }
20
21
    private void insert(int value, int[] nums, int length, int index) {
22
        for (int i = length; i > index; i--) nums[i] = nums[i - 1];
23
        nums[index] = value;
24
    }
25
}

解法2

逆向迭代,看起来好多了。不过时间复杂度其实差不多。

1
public class Solution {
2
3
    public void merge(int[] nums1, int m, int[] nums2, int n) {
4
        int i1 = m - 1;
5
        int i2 = n - 1;
6
        int now = m + n - 1;
7
        while (i1 > -1 && i2 > -1)
8
            nums1[now--] = (nums1[i1] > nums2[i2]) ? nums1[i1--] : nums2[i2--];
9
        while (i2 > -1) nums1[now--] = nums2[i2--];
10
    }
11
}