88. Merge Sorted Array
Array, Two Pointers, Sorting, Binary Search ·Problem Statement
link: LeetCode.cn LeetCode
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.
Example:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Solution Approach
The solution efficiently merges the two arrays by comparing elements from the end and placing them in the correct position within nums1 to maintain the sorted order.
Algorithm
Complexity
time complexity: O(m + n) space complexity: O(1)
Implement
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
l = m + n
cur = l - 1
i, j = m - 1, n - 1
while j >= 0 and i >= 0:
if nums1[i] >= nums2[j]:
nums1[cur] = nums1[i]
i -= 1
else:
nums1[cur] = nums2[j]
j -= 1
cur -= 1
while j >= 0:
nums1[cur] = nums2[j]
cur -= 1
j -= 1