[Java知识库]LeetCode88—合并两个有序数组（java版）

题目描述：

标签：数组? 双指针? 排序

给你两个有序整数数组?nums1 和 nums2，请你将 nums2 合并到?nums1?中，使 nums1 成为一个有序数组。

初始化?nums1 和 nums2 的元素数量分别为?m 和 n 。你可以假设?nums1 的空间大小等于?m + n，这样它就有足够的空间保存来自 nums2 的元素。

代码：?

?思路分析：

1、要注意两个数组都是有序数组，且注意遍历顺序，如果从前往后遍历需要不停地移动nums1数组的元素，所以选择从后向前遍历，避免了移动元素的麻烦。定义merge=m+n-1

2、定义双指针pre1和pre2分别指向nums1非零元素的最后一个元素、nums2的最后一个元素。遍历数组nums1，有以下四种情况，

①当pre2>0,pre1<0时，则把nums2中剩余元素加入nums1

②当pre1>0，pre2<0，则把nums1中剩余元素加入nums1

③当nums1[pre1] > nums2[pre2]，则把pre1指向的元素加入nums1

③当nums1[pre1] <?nums2[pre2]，则把pre2指向的元素加入nums1

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int pre1 = m - 1;
        int pre2 = n - 1;
        int merge = m + n - 1;
        while(pre2 >= 0){
            if(pre1 < 0){
                nums1[merge--] = nums2[pre2--];
            }else if(pre2 < 0){
                nums1[merge--] = nums1[pre1--];
            }else if(nums1[pre1] > nums2[pre2]){
                nums1[merge--] = nums1[pre1--];
            }else{
                nums1[merge--] = nums2[pre2--];
            }
        }
    }
}

?