leetcode 【 Merge Sorted Array 】python 实现
题目：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 Aa list of integers
3 # @param man integer, length of A
4 # @param Ba list of integers
5 # @param nan 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
12
13 while indexA >= 0 and indexB >= 0 :
14 if A > B:
15 A = A
16 indexA -= 1
17 else:
18 A = B
19 indexB -= 1
20 index_total -= 1
21
22 if indexA >= 0:
23 while indexA >= 0:
24 A = A
25 indexA -= 1
26 index_total -= 1
27 else:
28 while indexB >= 0:
29 A = B
30 indexB -= 1
31 index_total -= 1
思路：
采用最基础的两路归并思想。针对A B两个数组维护两个指针。
这里用到一个技巧是：从后往前遍历。
这样可以不用再开辟一个m+n空间的数组。
页:
[1]