leetcode--双指针5（88题/easy/java）

leetcode

按照模块刷题，点击进入使用的刷题目录

双指针

5.合并两个有序数组

题目描述：

合并两个有序数组

解题思路： 定义nums3数组，比较nums1和nums2的大小，将小的存放到nums3数组中，若其中一个数组中还有剩余数字，则全部拷贝到nums3数组中。最后将nums3拷贝至nums1数组。

代码:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3=new int[m+n];
        int i,j,k;
        for(i=0,j=0,k=0;i<m && j<n;++k){
            if(nums1[i]>nums2[j]){
                nums3[k]=nums2[j++];
            }
            else{
                nums3[k]=nums1[i++];
            }
        }
        while(i!=m){
            nums3[k++]=nums1[i++];
        }
        while(j!=n){
            nums3[k++]=nums2[j++];
        }
        for(i=0;i<m+n;++i){
            nums1[i]=nums3[i];
        }
    }
}
           

改进： 不需要设置nums3数组，从尾开始遍历，即可以避免nums1上归并得到的值会覆盖未进行归并比较的值的情况。

改进后的代码：

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