Make writing a habit together! This is the fourth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.
A, the title
You are given two non-descending arrays of integers, nums1 and nums2, and two integers, m and n, representing the number of elements in nums1 and nums2, respectively.
Please merge nums2 into nums1 so that the merged array is also in non-descending order.
Note: Finally, the merged array should not be returned by the function, but stored in the array nums1. To deal with this, nums1 has an initial length of m + n, where the first m elements represent the elements that should be combined and the last n elements are 0 and should be ignored. Nums2 has a length of n.
By LeetCode: leetcode-cn.com/leetbook/re… Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.
The sample1: Input: nums1 = [1.2.3.0.0.0], m = 3, nums2 = [2.5.6], n = 3Output:1.2.2.3.5.6] Explanation: need to merge [1.2.3] and [2.5.6]. The combined result is [1.2.2.3.5.6], where the elements in italic bold are nums1. The sample2: Input: nums1 = [1], m = 1, nums2 = [], n = 0Output:1] Explanation: need to merge [1] and []. The combined result is [1]. The sample3: Input: nums1 = [0], m = 0, nums2 = [1], n = 1Output:1The arrays to merge are [] and [].1]. The combined result is [1]. Notice, because m is equal to0So there are no elements in nums1. Only existing in NUMs10Just to make sure that the merge results can be safely stored in NUMs1.Copy the codeSecond, the train of thought
Idea 1
-
The problem here is that you have to change the NUM1 array
-
Slice was tried, which by itself did not alter the array, and although it got the same result, it did not pass the test case
-
So SPLice
-
splice
-
Parameter 1, mandatory, specifies the starting location for deletion and addition
-
Parameter 2, optional, number of items to delete
-
Parameter 3, which can be multiple new items to add to the array
-
After merging the arrays, use sort
-
Don’t need to return
Idea 2
-
Define p1 as num1, p2 as num2,
-
In the sorted array of length m+n, the current value is cur
-
Determine if conditions P1 <m or P2 <n are not true and terminate the loop
-
Check that if m is 0, then the array is num2
-
If n is 0, the array is num1
-
Num1 [p1]> num2[p2] if m and n are not 0
-
Cur = num2[p2++]
-
[p1++]
-
The array is sorted[m+n-1] = cur, which is -1 because subscripts start at 0
-
We then assign sorted to NUM1 in a loop
Three, code,
Code 1
let nums1 = [1.2.3.0.0.0], m = 3, nums2 = [2.5.6], n = 3
let merge = function(nums1, m, nums2, n) {
/** * There is a problem here that the num1 array must be changed ** Tried slice, which did not change the array itself, although the result is the same, but did not pass the test case * so the splice * splice * argument 1, mandatory, 2, optional, number of items to delete * 3, new items to add to the array, you can merge multiple * * arrays, use sort, do not return * */nums1.splice(m, nums1.length - m, ... nums2) nums1.sort((a, b) = > a - b)
}
merge(nums1, m, nums2, n)
Copy the codeCode 2
let nums1 = [1.2.3.0.0.0], m = 3, nums2 = [2.5.6], n = 3
let merge = function(nums1, m, nums2, n) {
/ / double pointer
** select a sorted array with a length of m+n and a sorted array with a length of m+n. ** select a sorted array with a length of m and a sorted array with a length of m+n. Num1 [p1]> num2[p2] * Cur = num2[p2++] * Cur = num2[P1 ++] * Cur = num2[M +n-1] = Cur -1 because the subscript starts at 0 * * and then loops to num1 * * */
let p1 = 0, p2 = 0
const sorted = new Array(m + n).fill(0)
let cur
while (p1 < m || p2 < n) {
if(p1 == m) {
cur = nums2[p2++]
} else if (p2 == n) {
cur = nums1[p1++]
} else if(nums1[p1] < nums2[p2]) {
cur = nums1[p1++]
} else {
cur = nums2[p2++]
}
sorted[p1+p2-1] = cur
}
sorted.map((item,index) = > nums1[index] = item)
}
merge(nums1, m, nums2, n)
Copy the code
