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

標籤

2015年12月27日 星期日

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

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

方法:
可能之一的演算法如下:
考慮已經 ab 排序過後的結果存放於序列 c, 將其元素一一分配到 de 序列使其兩個序列的合的差值為最小:
1. 依序從序列 c 取出兩個元素
2. 計算目前 de 序列中元素的合 d_sum 與 e_sum.
3. 如果 d_sum > e_sum, 則將取出的第一個元素放到 d 序列, 第二個元素加到 e 序列; 反之則將第一個元素加到 e 序列, 第二個元素加到 d 序列.
4. 反覆步驟 1-3 直到 c 序列所有元素都分配到de 序列。

範例代碼如下:
  1. #!/usr/bin/env python  
  2. tests = [[1,2,3,4,5,6,700,800],  
  3.          [10001,10000,100,90,50,1],  
  4.          range(111),  
  5.          [123121231123221030293211]]  
  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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!