Codility Tape Equilibrium in Python

  • Shuwei Zhang & Jinhai ZHOU
  • 2 Minutes
  • 2017年5月31日

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N) O(1)
平均 O(N) O(1)
最差 O(N) O(1)

算法分析

构造数组前段总和first = A[0]以及数组后端总和last = sum(A) - A[0],第一个差值便是abs(first - last)。遍历数组时,不必每次都重新构造数组前段总和以及数组后端总和,只需向first增加当前遍历元素,想las减去当前遍历元素,另外,也只要一个变量min_diff来记录最小差值即可。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
def solution(A):
# write your code in Python 2.7
first = A[0]
last = sum(A) - A[0]
N = len(A)
min_diff = abs(first - last)
for i in xrange(1, N - 1):
num = A[i]
first += num
last -= num
min_diff = min(abs(first - last), min_diff)
return min_diff