LeetCode 솔루션 분류
[Easy - wk3 - Q3] 88. Merge Sorted Array
본문
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.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The arrays we are merging are [1] and []. The result of the merge is [1].
Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
Constraints:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
Follow up: Can you come up with an algorithm that runs in O(m + n)
time?
관련자료
-
링크
댓글 3
Jack님의 댓글
- 익명
- 작성일
python
Runtime: 30 ms, faster than 98.58% of Python3 online submissions for Merge Sorted Array.
Memory Usage: 13.9 MB, less than 38.93% of Python3 online submissions for Merge Sorted Array
Runtime: 30 ms, faster than 98.58% of Python3 online submissions for Merge Sorted Array.
Memory Usage: 13.9 MB, less than 38.93% of Python3 online submissions for Merge Sorted Array
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.
"""
p1 = m - 1
p2 = n - 1
for i in range(m+n-1,-1,-1):
if p2 < 0:
break
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[i] = nums1[p1]
p1 -= 1
else:
nums1[i] = nums2[p2]
p2 -= 1
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Merge Sorted Array.
Memory Usage: 9 MB, less than 90.31% of C++ online submissions for Merge Sorted Array.
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Merge Sorted Array.
Memory Usage: 9 MB, less than 90.31% of C++ online submissions for Merge Sorted Array.
class Solution {
public:
void merge(vector<int>& nums1, int n1, vector<int>& nums2, int n2) {
int size = n1-- + n2-- - 1;
while (n1 >= 0 || n2 >= 0) {
if (n1 < 0) nums1[size--] = nums2[n2--];
else if (n2 < 0) nums1[size--] = nums1[n1--];
else nums1[size--] = nums1[n1] > nums2[n2] ? nums1[n1--] : nums2[n2--];
}
}
};
dawn27님의 댓글
- 익명
- 작성일
JS
Runtime: 67 ms, faster than 77.95% of JavaScript online submissions for Merge Sorted Array.
Memory Usage: 41.9 MB, less than 86.92% of JavaScript online submissions for Merge Sorted Array.
Runtime: 67 ms, faster than 77.95% of JavaScript online submissions for Merge Sorted Array.
Memory Usage: 41.9 MB, less than 86.92% of JavaScript online submissions for Merge Sorted Array.
var merge = function(nums1, m, nums2, n) {
// nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
// output = [1,2,2,3,5,6]
let first = m-1;
let second = n-1;
let i = m+n-1;
//퍼스트가 세컨보다 작다는 커디션을 먼저 적을때 에러 뜸
// while (second >= 0) {
// if (nums1[first] < nums2[second]) {
// nums1[i] = nums2[second];
// second--;
// i--;
// } else {
// nums1[i] = nums1[first];
// first--;
// i--;
// }
//}
while (second >= 0) {
let fVal = nums1[first];
let sVal = nums2[second];
if (fVal > sVal) {
nums1[i] = fVal;
first--;
i--;
} else {
nums1[i] = sVal;
second--;
i--;
}
}