[ Python 考題 ] 華為面試題 - 求兩序列的和最小差值序列

Source From Here
題目:
有兩個序列 a, b，大小都為 n,序列元素的值任意整形數，無序；要求：通過交換 a,b 中的元素，使 [序列 a 元素的和] 與 [序列 b 元素的和] 之間的差最小。

方法:
可能之一的演算法如下:
考慮已經 a, b 排序過後的結果存放於序列 c, 將其元素一一分配到 d, e 序列使其兩個序列的合的差值為最小:

1. 依序從序列 c 取出兩個元素
2. 計算目前 d, e 序列中元素的合 d_sum 與 e_sum.
3. 如果 d_sum > e_sum, 則將取出的第一個元素放到 d 序列, 第二個元素加到 e 序列; 反之則將第一個元素加到 e 序列, 第二個元素加到 d 序列.
4. 反覆步驟 1-3 直到 c 序列所有元素都分配到d, e 序列。

範例代碼如下:

view plaincopy to clipboardprint?

1. #!/usr/bin/env python  
2. tests = [[1,2,3,4,5,6,700,800],  
3.          [10001,10000,100,90,50,1],  
4.          range(1, 11),  
5.          [12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]]  
6.   
7. for c in tests:  
8.     c.sort()  
9.     a = []  
10.     b = []  
11.     # Approach 1  
12.     #for i in range(len(c)/2):  
13.     #    if (i%2) == 0:  
14.     #        a.append(c[i*2])  
15.     #        b.append(c[i*2+1])  
16.     #    else:  
17.     #        b.append(c[i*2])  
18.     #        a.append(c[i*2+1])  
19.   
20.     # Approach 2  
21.     for i in range(len(c)/2):  
22.         a_sum = reduce(lambda x,y:x+y, a, 0)  
23.         b_sum = reduce(lambda x,y:x+y, b, 0)  
24.         if a_sum > b_sum:  
25.             a.append(c[i*2])  
26.             b.append(c[i*2+1])  
27.         else:  
28.             b.append(c[i*2])  
29.             a.append(c[i*2+1])  
30.   
31.     print("C= %s" % c)  
32.     print("A= %s" % a)  
33.     print("B= %s" % b)  
34.   
35.     a_sum = reduce(lambda x,y:x+y, a)  
36.     b_sum = reduce(lambda x,y:x+y, b)  
37.     print("A sum to %d; B sum to %d; Diff=%d" % (a_sum, b_sum, abs(a_sum-b_sum)))  

執行結果如下:

# ./intv_q1.py
C= [1, 2, 3, 4, 5, 6, 700, 800]
A= [2, 3, 6, 700]
B= [1, 4, 5, 800]
A sum to 711; B sum to 810; Diff=99
========================
C= [1, 50, 90, 100, 10000, 10001]
A= [50, 90, 10000]
B= [1, 100, 10001]
A sum to 10140; B sum to 10102; Diff=38
========================
C= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
A= [2, 3, 6, 7, 10]
B= [1, 4, 5, 8, 9]
A sum to 28; B sum to 27; Diff=1
========================
C= [1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312]
A= [1, 3, 29, 232, 12311]
B= [1, 2, 30, 210, 12312]
A sum to 12576; B sum to 12555; Diff=21
========================

This message was edited 5 times. Last update was at 28/12/2015 10:23:41