leetcode 【 Merge Sorted Array 】python 实现

浏览数：27 / 时间：2015年06月08日

题目：

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
12         
13         while indexA >= 0 and indexB >= 0 :
14             if A[indexA] > B[indexB]:
15                 A[index_total] = A[indexA]
16                 indexA -= 1
17             else:
18                 A[index_total] = B[indexB]
19                 indexB -= 1
20             index_total -= 1
21         
22         if indexA >= 0:
23             while indexA >= 0:
24                 A[index_total] = A[indexA]
25                 indexA -= 1
26                 index_total -= 1
27         else:
28             while indexB >= 0:
29                 A[index_total] = B[indexB]
30                 indexB -= 1
31                 index_total -= 1

 

思路：

采用最基础的两路归并思想。针对A B两个数组维护两个指针。

这里用到一个技巧是：从后往前遍历。

这样可以不用再开辟一个m+n空间的数组。

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢