88. Merge Sorted Arrays

https://leetcode.com/problems/merge-sorted-array/

solution

• 双指针

  • 为了在nums1原位置修改，从尾到头进行merge

# 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
        # destination d index to insert into nums1
        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)

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

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

follow-up

23. Merge k Sorted Lists

Merge 3 sorted array

• 可以两两merge

Merge two sorted linked list without duplicates

K-th Element of Merged Two Sorted Arrays