leetcode-88-easy

Merge Sorted Array
思路一: 比较两个数组前面最小值，依次插入到新数组中，最后复制新数组到 num1 中

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] result = new int[nums1.length];

    int i = 0;
    int x = 0;
    int y = 0;
    int valY;
    int valX;
    while (i < nums1.length) {
        if (y < n) {
            valY = nums2[y];
        } else {
            valY = Integer.MAX_VALUE;
        }

        if (x < m) {
            valX = nums1[x];
        } else {
            valX = Integer.MAX_VALUE;
        }

        if (valX < valY) {
            x++;
            result[i] = valX;
        } else {
            y++;
            result[i] = valY;
        }

        i++;
    }

    for (i = 0; i < result.length; i++) {
        nums1[i] = result[i];
    }
}

思路二: 从数组后面开始比较，可以在 nums1 数组上直接操作，比思路一少了额外的数组内存申请

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = nums1.length - 1;
    int x = m - 1;
    int y = n - 1;
    while (i >= 0) {
        if (x < 0 || y < 0) break;

        if (nums1[x] > nums2[y]) {
            nums1[i--] = nums1[x--];
        } else {
            nums1[i--] = nums2[y--];
        }
    }

    while (x >= 0 && i >= 0) {
        nums1[i--] = nums1[x--];
    }
    while (y >= 0 && i >= 0) {
        nums1[i--] = nums2[y--];
    }
}