88. Merge Sorted Array

1.問題

• 給予兩個sorted list, 將nums2 merge到num1

2.想法

• 提問

  • 確認題意: 將輸入的兩個字串轉為數字相乘並返回對應的字串

• function header, parameter

• test input

• 說明想法

  • 第二種做法是比較兩個list, 將較大者從list 1的最後放入, 由於目的是將list 2完全放入, 因此當list 2的index為0時, 迴圈結束

• 測試計算複雜度

3.程式碼

• 方法1

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int r = m + n -1, index1 = m - 1, index2 = n -1;
        while (index1 >= 0 && index2 >= 0){
            if (nums1[index1] >= nums2[index2]) {
                nums1[r] = nums1[index1];
                index1--;
                r--;
            } else {
                nums1[r] = nums2[index2];
                index2--;
                r--;
            }
        }
        
        while (index1 >= 0){
            nums1[r] = nums1[index1];
            index1--;
            r--;
        }
        
        while (index2 >= 0){
            nums1[r] = nums2[index2];
            index2--;
            r--;
        }
        
    }
};

• 方法2

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
        }
        int idx = m + n - 1, idx1 = m - 1, idx2 = n -1;
        while (idx2 >= 0) {
            if (idx1 >=0 && nums1[idx1] >= nums2[idx2]) {
                nums1[idx--] = nums1[idx1--];
            } else {
                nums1[idx--] = nums2[idx2--];
            }
        }
        
    }
};