LeetMotion
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 nums2 into nums1 as one sorted array. 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 last n elements are set to 0 and should be ignored.
nums1. Merge from the BACK instead — the empty zeros at the end of nums1 give you safe write space.p1 reads from the valid end of nums1, p2 reads from the end of nums2, and p writes to the very end of nums1.p1 goes below 0 (nums1 exhausted), just copy the remaining nums2elements directly — they're already in sorted order.Two stacks of sorted cards face-down. Peek at the top of each — take the larger one and place it in the last empty slot of the combined stack. Repeat until one stack is empty, then copy the rest.
The most intuitive and naïve solution is to simply copy all the elements of nums2 into the back of nums1 (which has enough empty space filled with 0s). Once all elements are in a single array, we just sort that array using a built-in sorting method.
nums1 has length m + n, copy elements from nums2 into indexes m to m + n - 1 in nums1.nums1.Why it's not optimal: Sorting takes O((m+n) log(m+n)) time. This approach completely ignores the fact that nums1 and nums2 are already sorted, wasting a lot of computation.
def merge(nums1, m, nums2, n): for i in range(n): nums1[m + i] = nums2[i] nums1.sort()
Instead of merging from the front (which risks overwriting unread nums1 values), we merge from the back. The trailing zeros at the end of nums1 are safe write space.
p1 = m-1 (end of valid nums1), p2 = n-1 (end of nums2), p = m+n-1 (write position).p2 ≥ 0: compare nums1[p1] and nums2[p2]. Place the larger at nums1[p], decrement the corresponding pointer.p after each placement.p1 < 0, remaining nums2 elements go straight into nums1.
Discussion
…