题目：
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and nrespectively.
代码：oj测试通过 Runtime: 58 ms
1
class
Solution:
2
#
@param A a list of integers
3
#
@param m an integer, length of A
4
#
@param B a list of integers
5
#
@param n an integer, length of B
6
#
@return nothing
7
def
merge(self, A, m, B, n):
8
9 index_total = m + n - 1
10 indexA = m-1
11 indexB = n-1
1213while indexA >= 0 and indexB >= 0 :
14if A[indexA] > B[indexB]:
15 A[index_total] = A[indexA]
16 indexA -= 1
17else:
18 A[index_total] = B[indexB]
19 indexB -= 1
20 index_total -= 1
2122if indexA >= 0:
23while indexA >= 0:
24 A[index_total] = A[indexA]
25 indexA -= 1
26 index_total -= 1
27else:
28while indexB >= 0:
29 A[index_total] = B[indexB]
30 indexB -= 1
31 index_total -= 1
思路：
采用最基础的两路归并思想。针对A B两个数组维护两个指针。
这里用到一个技巧是：从后往前遍历。
这样可以不用再开辟一个m+n空间的数组。
原文：http://www.cnblogs.com/xbf9xbf/p/4240257.html
【说明】：本文章由站长整理发布，文章内容不代表本站观点，如文中有侵权行为，请与本站客服联系(QQ:254677821)！