Leetcode # 88. Merge Sorted Array

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

First Solution

從尾到頭逆著做回來

Time Complexity: O(m + n)
Space Complexity: O(1)

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

Solution: Two Pointers

Time Complexity: O(m + n)
Space Complexity: O(1)

class Solution:
  def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    """
    Do not return anything, modify nums1 in-place instead.
    """
    i = j = k = 0
    while i < m and j < n:
      # do some logic here
      if nums1[i] < nums2[j]:
        nums1[k] = nums1[i]
      else:
        nums1[k], nums2[j] = nums2[j], nums1[i]
        _j = j
        while _j + 1 < n and nums2[_j] > nums2[_j + 1]:
          nums2[_j], nums2[_j + 1] = nums2[_j + 1], nums2[_j]
          _j += 1
      i += 1
      k += 1

    """
    while i < m:
      # do logic
      i += 1
    """

    while j < n:
      # do logic
      nums1[k] = nums2[j]
      j += 1
      k += 1
    
    return nums1

Refined Solution: Two Pointers

效法 first solution 逆著做回來

Time Complexity: O(m + n)
Space Complexity: O(1)

class Solution:
  def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    """
    Do not return anything, modify nums1 in-place instead.
    """
    i, j, k = m - 1, n - 1, m + n - 1
    while i >= 0 and j >= 0:
      # do some logic here
      if nums1[i] > nums2[j]:
        nums1[k] = nums1[i]
        i -= 1
      else:
        nums1[k] = nums2[j]
        j -= 1
      k -= 1

    for l in range((i + 1) if i > 0 else (j + 1)):
      nums1[k - l] = nums1[i - l] if i > 0 else nums2[j - l]
    
    return nums1

Last Updated on 2023/08/16 by A1go