88. Merge Sorted Array

Đề bài cho hai mảng nums1 và nums2 có chiều dài là m và n. Yêu cầu merge hai mảng này mà không sử dụng thêm mảng mới.

VD: nums1 = [4, 5, 6, 0, 0, 0]; nums2 = [1, 2, 3]

Ý tưởng: Thay vì cố gắng duyệt từ đầu thì sẽ duyệt từ đuôi.

Duyệt từ đít của hai mảng nums1 và nums2. Thằng đít nào lớn hơn thì nhét vào cuối của nums1, rồi trừ index đi.

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.

"""

if m == 0:

nums1[:] = nums2

if n == 0:

return

i, j, k = m-1, n-1, m+n-1

while j >= 0:

if (i >= 0) and (nums1[i] > nums2[j]):

nums1[k] = nums1[i]

i-= 1

else:

nums1[k] = nums2[j]

j-= 1

k-= 1