Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- The number of elements initialized in nums1 and nums2 are m and n respectively.
- You may assume that nums1 has enough space (size that is greater or equal to m + n) 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]
给两个有序的数组 A 和 B，把 B 合并到 A，变成一个数组，假定 A 有足够的空间。
可以考虑新建立一个m + n的数组，然后从两个数组的开头取各取一个元素进行比较，把小的放进新数组，然后在循环这个过程，直到结束。
好的方法是不用新建立数组，而是直接在A 数组上写入，因为 A 足够大，可从两个数组的最大数也就是最后一个数开始比较，大的写入A[m + n -1]，然后循环这个过程。如果 B 的元素写完了，A 剩下的元素正好在正取的位置，不用写了。如果 A 的元素都取完了，那剩下的 B 的元素可一次全部写进 A。
Java:
public class Solution {
public void merge(int A[], int m, int B[], int n) {
while(m > 0 && n > 0){
if(A[m-1] > B[n-1]){
A[m+n-1] = A[m-1];
m--;
}else{
A[m+n-1] = B[n-1];
n--;
}
}
while(n > 0){
A[m+n-1] = B[n-1];
n--;
}
}
}
Java:
public void merge(int A[], int m, int B[], int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (k >= 0) {
if (j < 0 || (i >= 0 && A[i] > B[j]))
A[k--] = A[i--];
else
A[k--] = B[j--];
}
}
Python:
class Solution:
# @param A a list of integers
# @param m an integer, length of A
# @param B a list of integers
# @param n an integer, length of B
# @return nothing
def merge(self, A, m, B, n):
last, i, j = m + n - 1, m - 1, n - 1 while i >= 0 and j >= 0:
if A[i] > B[j]:
A[last] = A[i]
last, i = last - 1, i - 1
else:
A[last] = B[j]
last, j = last - 1, j - 1 while j >= 0:
A[last] = B[j]
last, j = last - 1, j - 1 if __name__ == "__main__":
A = [1, 3, 5, 0, 0, 0, 0]
B = [2, 4, 6, 7]
Solution().merge(A, 3, B, 4)
print(A)
Python:
class Solution:
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.
"""
while m > 0 and n > 0:
if nums1[m-1] > nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
if n > 0:
nums1[:n] = nums2[:n]
C++:
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m + n;
while (m > 0 && n > 0) {
if (nums1[m - 1] > nums2[n - 1]) {
nums1[i - 1] = nums1[m - 1];
--m;
} else {
nums1[i - 1] = nums2[n - 1];
--n;
}
--i;
}
while (n > 0) {
nums1[i - 1] = nums2[n - 1];
--n;
--i;
}
}
};
类似题目：
[LeetCode] 21. Merge Two Sorted Lists 合并有序链表
[LeetCode] 23. Merge k Sorted Lists 合并k个有序链表