###### tags: `Leetcode` `easy` `pointer` `python` `c++`

# 88. Merge Sorted Array

## [題目出處:] https://leetcode.com/problems/merge-sorted-array/

## 題目:
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

**Merge nums1 and nums2 into a single array sorted in non-decreasing order.**

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

## 解題想法:
* 此題為排序組合nums1、nums2於nums1中
* nums1長度為m+n，後面n格全都是0
-> 設兩pointer逐一比較nums1、nums2尾巴
-> pointer tail為len(nums)-1
-> 大的放入nums[tail]

## Python:

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        #runs in O(m + n)
        for i in range(1, m + n + 1):
            if n == 0:
                #nums2沒東西ㄌ
                print("case1")
                break
            elif m == 0:
                #nums1沒東西ㄌ
                #負數 往回數 -1 最後一個 -2 倒數第二個
                print('case2')
                #將nums2最後一值 塞到nums1最後面
                nums1[-i] = nums2[n-1]
                n = n- 1
                continue
            #不能用break!!! ex: nums1= [0,0] nums=[1,2]
            #continue會跳過本次迴圈剩下的程式碼，但不會結束迴圈，仍然會進入下一圈繼續執行
            if nums1[m - 1] < nums2[n - 1]:
                #若nums2最後一個的值 比nums1的值大 
                #!!! nums1最後值要用 m-1  不能用-i 因為-i裝的是0
                print('case3')
                nums1[-i] = nums2[n - 1]
                n = n- 1
            else:
                print('case4')
                #把nums1的值 丟到最後一個位置
                nums1[-i] = nums1[m - 1]
                m = m- 1
        return nums1
    
class Solution2(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        p1=m-1
        p2=n-1
        tail=m+n-1
        while p1>=0 and p2>=0:
            if nums1[p1]<=nums2[p2]:
                nums1[tail]=nums2[p2]
                tail-=1
                p2-=1
            else:
                nums1[tail]=nums1[p1]
                tail-=1
                p1-=1
        #nums2還有剩
        while p2>=0:
            nums1[tail]=nums2[p2]
            tail-=1
            p2-=1       
                 
if __name__ == '__main__':
    nums1 = [1,2,3,0,0,0]
    m = 3
    nums2 = [2,5,6]
    n = 3
    result = Solution()
    ans = result.merge(nums1,m,nums2,n)
    print(ans)

## C++:

#include<iostream>
#include<vector>
using namespace std;

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

int main(){
    vector<int>nums1={1,2,3,0,0,0};
    vector<int>nums2={2,5,6};
    int m=3;
    int n=3;
    Solution res;
    res.merge(nums1,m,nums2,n);
    for (int i=0; i<nums1.size(); i++){
        cout<<nums1[i]<<" ";
    }
    return 0;
}