Sign in

[Java][TwoPoints][LeetCode] Merge Sorted Array #88

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 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Two arrays are increase sequences. Back of nums1 are invalid elements. I can use two points and those invalid elements to keep the value that is larger in nums1 and nums2. Values start to keep from index length-1 to 0. Because, if I keep value from index 0, I need to shift those elements backward.

因為兩組數組都是已經由小到大排序,數組1與數組2的有效數字數量為m+n,數組1的後面是無效的0,所以可以利用雙指針來比較較大的數值,並把數值數組1的後面開始倒放,這樣就不會像從index 0開始比較而要擔心數組1被覆蓋到,如果從index 0開始比較,則需要將數組1的後面數值往後移。