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--];
        }
    }
}