【华为公司Python面试题】，要求10分钟写出代码。。。

inpool

思路：
合并两个列表，排序，然后按顺序从后往前每次取两个元素a, b，则a >= b
将取出来的数按a-b的值b进行分组
将分组按a-b的值排序然后合并，得到一个长为n的列表listab = [(a1,b1), (a2,b2), (a3,b3), ..., (an,bn)]
可证(listab[0] - listab[1]) >= (listab[i-1][0] - listab[i-1][1])  (0<= i < n)
定义两个空序列lista, listb
然后按从后往前的顺序取出listab的值并根据sum(lista)-sum(listb)的值，将ai,bi压入数组lista或listb
压入第一个时，abs(sum(lista) - sum(listb))最大，然后逐渐减小。
这个算法简单，实现也简单，思考5分钟，代码3-5分钟。

1. def min_sub_of_sum(lista, listb):
   
2.     listab = lista + listb
   
3.     listab.sort()
   
4.     tmp = {}
   
5.     while listab:
   
6.         a = listab.pop()
   
7.         b = listab.pop()
   
8.         tmp.setdefault(a-b, []).append((a, b))
   
9.     subs = tmp.keys()
   
10.     subs.sort()
    
11.     for sub in subs:
    
12.         listab.extend(tmp[sub])
    
13.     lista, listb = [], []
    
14.     # sub == sum(lista) - sum(listb)
    
15.     sub = 0
    
16.     while listab:
    
17.         if sub < 0:
    
18.             a, b = listab.pop()
    
19.         else:
    
20.             b, a = listab.pop()
    
21. 
    
22.         lista.append(a)
    
23.         listb.append(b)
    
24.         sub += (a - b)
    
25.     return lista, listb
    
26. 
    
27. 
    
28. if __name__ == '__main__':
    
29.     lista = range(100)
    
30.     listb = [i^11 for i in lista]
    
31.     a, b = min_sub_of_sum(lista, listb)
    
32.     print a
    
33.     print b
    
34.     print sum(a) - sum(b)

复制代码