Leetcode|Merge Sorted Array(2つの秩序配列を結合)
Description:
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.
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]
Ideas:
My Code:
Execution time:28 ms Memory consumption:13.1 MB
Official Method:
Execution time:20 ms Memery consumption:13.1 MB
summary
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.
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]
Ideas:
Oh, first of all, I must remind you guys, this problem return nums1 default. So you cant return user-defined list.
In python, you should remember sorted() function. Of course we can merge two array and reorder it.
Second method is using pointer, but after I saw the official one, I would say that most of us havent
make use of the problem condition. The two array are already sorted and nums1 have n nodes extra space.
If you traverse the list from back and you can modify nums1 direct, In this way, you can save O(m-1) space complexity.
My Code:
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 in-place instead.
"""
idx1, idx2 = 0, 0
nums1_copy = nums1[:m]
nums1[:] = []
while idx1 < m and idx2 < n:
x = nums1_copy[idx1]
y = nums2[idx2]
if x > y:
nums1.append(y)
idx2 += 1
else:
nums1.append(x)
idx1 += 1
if idx1 < m:
nums1.extend(nums1_copy[idx1:])
elif idx2 < n:
nums1.extend(nums2[idx2:])
Execution time:28 ms Memory consumption:13.1 MB
Official Method:
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
# two get pointers for nums1 and nums2
p1 = m - 1
p2 = n - 1
# set pointer for nums1
p = m + n - 1
# while there are still elements to compare
while p1 >= 0 and p2 >= 0:
if nums1[p1] < nums2[p2]:
nums1[p] = nums2[p2]
p2 -= 1
else:
nums1[p] = nums1[p1]
p1 -= 1
p -= 1
# add missing elements from nums2
nums1[:p2 + 1] = nums2[:p2 + 1]
:LeetCode
:https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/
: (LeetCode)
Execution time:20 ms Memery consumption:13.1 MB
summary
If we can modify it in origional sapce, try not to create extra space to solve problem.