# 0088. Merge Sorted Array
###### tags: `Leetcode` `Easy` `FaceBook`
Link: https://leetcode.com/problems/merge-sorted-array/
## 思路
### 思路一 $O(m+n)$ $O(1)$
很tricky的一道题
一开始的想法是一个一个比较 然后从最左边开始 但这样就可能会覆盖到还没排列的数据
因此 看了答案之后 发现更好的做法是**用三个pointer，从后往前填数字**
两个阵列从最尾端开始 谁比较大 谁放进nums1里面，直到nums2里面的数据都放完了，nums1也不需要再处理了，因为剩下的部分也已经排好顺序了
**总结下来就是 跟数字相关的题想想倒着来（例如之前移到rotate array的题 把array翻转一下就解了）**
### 思路二
后来做题的时候想到的，类似双指针的做法，（一个指针指向下一个即将被排序的数字应该放在nums1的哪里，一个指向nums2的第一个数字）一个一个比较，如果nums1里面的数字比较小，那么指向nums1的指针往右移一个，如果nums2里面的数字比较小，就把这个数字跟nums1里面的数字调换位置，然后把nums2排序，保证nums2永远是从小到大排的，一直比到nums1没有数字了（因为nums1里面永远只会有m个数字，那么就把nums2的数字全部接在后面）
## Code
### 思路一
Java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m-1;
        int p2 = n-1;
        for(int p = m+n-1;p >= 0;p--){
            if(p2<0) break;
            if(p1>=0 && nums1[p1]>nums2[p2]){
                nums1[p] = nums1[p1];
                p1--;
            }
            else{
                nums1[p] = nums2[p2];
                p2--;
            }
        }

    }
}

C++

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

### 思路二

int i = 0, temp;
        while(i!=m){
            if(nums1[i]>nums2[0]){
                temp = nums1[i];
                nums1[i] = nums2[0];
                nums2[0] = temp;
                i++;
                Arrays.sort(nums2);
            }
            else{
                i++;
            }
        }
        for(int j = m;j < nums1.length;j++){
            nums1[j] = nums2[j-m];
        }

## Result
### 思路一
Runtime: 0 ms, faster than **100.00%** of C++ online submissions for Merge Sorted Array.
Memory Usage: 9.1 MB, less than **60.10%** of C++ online submissions for Merge Sorted Array.
### 思路二
Your runtime beats **93.30 %** of java submissions.
Your memory usage beats **99.77 %** of java submissions.