LintCode Q464 Sort Integers II merge in Python

  • Jinhai ZHOU
  • 5 Minutes
  • 2016年11月11日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
# @param {int[]} A an integer array
# @return nothing
def sortIntegers2(self, A):
# Write your code here
# merge sort
# Total Runtime: 2306 ms
# 100% test cases passed.
aux = [0]*len(A) # auxiliary array
self.mergeSort(A, aux, 0, len(A)-1)
def mergeSort(self, A, aux, lo, hi):
if hi <= lo:
return
# Python has arbitrary precision integers
# ints are automatically promoted to long
# so there is no integer overflow when doing
# mid = (lo + hi)/2
# in Java, it's better to mid = lo + (hi - lo)/2
mid = (lo + hi)/2
self.mergeSort(A, aux, lo, mid)
self.mergeSort(A, aux, mid + 1, hi)
self.merge(A, aux, lo, mid, hi)
def merge(self, A, aux, lo, mid, hi):
for k in xrange(lo, hi + 1):
aux[k] = A[k]
i, j = lo, mid + 1
for k in xrange(lo, hi + 1):
if i > mid:
A[k] = aux[j]
j += 1
elif j > hi:
A[k] = aux[i]
i += 1
elif aux[j] < aux[i]:
A[k] = aux[j]
j += 1
else:
A[k] = aux[i]
i += 1
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。