# Python俱乐部

## 链接

algorithm:huawei-interview

# 华为面试题

## 求两序列的和最小差值序列

### 算法

1. 将两序列合并为一个序列，并排序，为序列Source

2. 拿出最大元素Big，次大的元素Small

3. 在余下的序列S[:-2]进行平分，得到序列max，min

4. 将Small加到max序列，将Big加大min序列，重新计算新序列和，和大的为max，小的为min。

### python实现代码

```def mean( sorted_list ):
if not sorted_list:
return (([],[]))

big = sorted_list[-1]
small = sorted_list[-2]
big_list, small_list = mean(sorted_list[:-2])

big_list.append(small)
small_list.append(big)

big_list_sum = sum(big_list)
small_list_sum = sum(small_list)

if big_list_sum > small_list_sum:
return ( (big_list, small_list))
else:
return (( small_list, big_list))

tests = [   [1,2,3,4,5,6,700,800],
[10001,10000,100,90,50,1],
range(1, 11),
[12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]
]
for l in tests:
l.sort()
print
print "Source List:\t", l
l1,l2 = mean(l)
print "Result List:\t", l1, l2
print "Distance:\t", abs(sum(l1)-sum(l2))
print '-*'*40```

### 输出结果

```Source List:    [1, 2, 3, 4, 5, 6, 700, 800]
Result List:    [1, 4, 5, 800] [2, 3, 6, 700]
Distance:       99
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

Source List:    [1, 50, 90, 100, 10000, 10001]
Result List:    [50, 90, 10000] [1, 100, 10001]
Distance:       38
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

Source List:    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Result List:    [2, 3, 6, 7, 10] [1, 4, 5, 8, 9]
Distance:       1
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

Source List:    [1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312]
Result List:    [1, 3, 29, 232, 12311] [1, 2, 30, 210, 12312]
Distance:       21
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*```
algorithm/huawei-interview.txt · 最后更改: 2010/06/02 01:18 (外部编辑)