# 88. Merge Sorted Arrays

[https://leetcode.com/problems/merge-sorted-array/](https://leetcode.com/problems/merge-sorted-array/)

## solution

* 双指针
  * 为了在nums1原位置修改，从尾到头进行merge

```python
# https://walkccc.me/LeetCode/problems/0088/

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1, p2 = m - 1, n - 1
        for d in range(m + n - 1, -1, -1):
            # if second list is empty, nothing more to merge
            if p2 < 0:
                return
            # only merge from nums1 if there are items left to merge
            # insert at d the larger of the two values from nums1 and nums2
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[d] = nums1[p1]
                p1 -= 1
            else:
                nums1[d] = nums2[p2]
                p2 -= 1
```

时间复杂度：O(m+n)\
空间复杂度：O(1)

```python
class Solution:
    def mergeSortedArray(self, A, m, B, n):
        index = m + n - 1
        i = m - 1
        j = n - 1

        while i >=0 and j >= 0:
            if A[i] >= B[j]:
                A[index] = A[i]
                i -= 1
            else:
                A[index] = B[j]
                j -= 1
            index -= 1

        while i >= 0:
            A[index] = A[i]
            i -= 1
            index -= 1

        while j >= 0:
            A[index] = B[j]
            j -= 1
            index -= 1
```

* heap

```python
```

时间复杂度：O()\
空间复杂度：O()

## follow-up

[23. Merge k Sorted Lists](../06_heap/23.-merge-k-sorted-lists)

[Merge 3 sorted array](https://www.geeksforgeeks.org/merge-3-sorted-arrays/)

* 可以两两merge

[Merge two sorted linked list without duplicates](https://www.geeksforgeeks.org/merge-two-sorted-linked-list-without-duplicates/)

[K-th Element of Merged Two Sorted Arrays](https://www.geeksforgeeks.org/k-th-element-two-sorted-arrays/)
