# 88. Merge Sorted Array

## 1.問題 

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNcivxVEXEeloBWtcTW%2F-LNd2zN4dhRr8AgMyKTS%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-30%20%E4%B8%8B%E5%8D%881.59.42.png?alt=media\&token=90879f9d-da33-44d6-a9ba-1cfa4875e6c6)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意:  將輸入的兩個字串轉為數字相乘並返回對應的字串
* function header, parameter
* test input
* 說明想法
  * 第二種做法是比較兩個list, 將較大者從list 1的最後放入, 由於目的是將list 2完全放入, 因此當list 2的index為0時, 迴圈結束
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

* **方法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--];
            }
        }
        
    }
};
```