LeetCode 88. Merge Sorted Array 歸并的過程

Given two sorted integer arrays nums1 and nums2, merge nums2 intonums1 as one sorted array.

題意:對于有序的兩個數組nums1，nums2進行歸并到nums1裡保持其有序性

1.按照歸并排序進行歸并的過程，需要單獨開辟一塊空間O（n），時間複雜度O(n)

2.在進行歸并的過程，需要注意越界的情況，當其中之一的數組已經歸并完畢，剩餘的元素就是另外一個數組的元素

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

優化1：

1.上述代碼使用了空間複雜度O（n），是因為忽略了一個條件，nums1的長度為(n+m)

2.從後往前指派，比較歸并

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, tar = m + n - 1;
	    while (j >= 0) {
    		nums1[tar--] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
	    }
    }
};