LeetCode刷題筆記-合并兩個有序數組

合并兩個有序數組

給你兩個有序整數數組 nums1 和 nums2，請你将 nums2 合并到 nums1 中，使 nums1 成為一個有序數組。

初始化 nums1 和 nums2 的元素數量分别為 m 和 n 。你可以假設 nums1 的空間大小等于 m + n，這樣它就有足夠的空間儲存來自 nums2 的元素。

示例 1：

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
           

示例 2：

輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
 
           

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <=200
• -109 <= nums1[i], nums2[i] <= 109

思路：

用一個輔助數組nums3,然後分别用i，j指針指向nums1,nums2,

比較 nums[i] , nums2[j] 的值

t指針更新nums3的值

如果i=m 或者 j=n則代表兩個數組有一個比較完了，此時隻需要将另外一個數組的值直接拷貝進nums3

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //開辟一個m+n的輔助空間
		int[]  nums3=new int[m+n];
        int i=0,j=0,t=0;
        while(t<(m+n)){
            if (i==m) { while(j<n){nums3[t]=nums2[j]; t++;j++;} break;}
			if (j==n) { while(i<m){nums3[t]=nums1[i] ;t++;i++;} break;}
            if( nums1[i]<nums2[j] ) { 
                nums3[t]=nums1[i];
                i++; 
                t++;
            }else if(nums1[i]==nums2[j]){ 
                nums3[t]=nums1[i];
                nums3[t+1]=nums2[j];
                i++;j++;t+=2;
            }else {
                nums3[t]=nums2[j];
                t++;
                j++;
            }
        }
        for(int k=0;k<nums3.length;k++){
            nums1[k]=nums3[k];
        } 
    }
}