算法-四等分数组-阿里2017年研发工程师JAVA(实习生)编程笔试

题目描述

给定一维数组arr,其元素都为正数,将其分为4个组,4个组的和分别相等,并且不包含分割位置的元素。判断给定数组是否符合该条件。

可能解法(python版)

算法思想:将数组分为4个部分,共存在3个分界点。初始化3个分界点的合理位置,使得每一段都非空,同时初始化4个部分的和。从左边和右边开始扫描调整分界点位置,直到第1部分和第4部分相等。算法接着调整第2部分和第3部分,使得它们的部分和也相等。至此,可以比较第1段和第2段的和,如果满足第1段大于第2段,则不再有调整的可能,否则接着调整。算法利用了两个重要特征:

  • 数组中所有元素都是正数,因此加上一个数不会变小;
  • 第1段和第4段的和都是从小往大递增的。
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
42
43
44
def fourPartition(arr):
first, second, third = 1, len(arr)/2, len(arr) - 2
sum1 = sum2 = sum3 = sum4 = 0
# requires only one sweep
sum1 += sum(arr[0:first])
sum2 += sum(arr[(first + 1):second])
sum3 += sum(arr[(second + 1):third])
sum4 += sum(arr[third + 1:])
if sum1 * sum2 * sum3 * sum4 == 0:
return False
while(first < second - 1) and (second < third - 1):
#sum1 and sum4, from small to large, until equal
if sum1 < sum4:
sum1 += arr[first]
sum2 -= arr[first + 1]
first += 1
elif sum1 > sum4:
sum4 += arr[third]
sum3 -= arr[third - 1]
third -= 1
#sum1 == sum4
else:
if sum2 < sum3:
sum2 += arr[second]
sum3 -= arr[second + 1]
second += 1
elif sum2 > sum3:
sum2 -= arr[second - 1]
sum3 += arr[second]
second -= 1
#sum2 == sum3
else:
if sum1 < sum2:
sum1 += arr[first]
sum2 -= arr[first + 1]
first += 1
elif sum1 > sum2:
return False
#sum1 == sum2
else:
return True
return False

复杂度分析

算法时间复杂度为$\mathcal{O}(n)$,空间复杂度也为$\mathcal{O}(N)$。

文章目录
  1. 1. 题目描述
  2. 2. 可能解法(python版)
  3. 3. 复杂度分析
|