传闻中的华为Python面试题（原创）

lsdwyl

　　原题:
有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小

　　限时十分钟以内
　　
　　尝试解答，coding和debug共用了约1个小时，呵呵，去不了华为了。
获取最小差的函数，还可以优化，现在的时间复杂度是n×n，估计可以优化到n×lg(n)
　　
　　网上有一种解答方法，认为最小值是负数，排序之后，截成两段，小数序列-大数序列即可。难道，难道，这才是本题十分钟解出的奥义？！
　　我的代码如下，算法很简单（我的算法不对，请列位看官参考评论中张三的）：
　　
　　

'''
Created on 2010-6-21
@author: maodouzi
'''
import random
def getMinSubKeys(leftArray, rightArray):
if (sum(leftArray) > sum(rightArray)):
subArray = leftArray
minuendArray = rightArray
subFlag = True
elif (sum(leftArray) < sum(rightArray)):
subArray = rightArray
minuendArray = leftArray
subFlag = False
else:
return None
minSubNum = (sum(subArray) - sum(minuendArray)) / 2.0
tmpMinSubResult = sum(subArray)
subKey = 0
minuendKey = 0
for i_key, i in enumerate(subArray):
for j_key, j in enumerate(minuendArray):
if (abs(i - j - minSubNum) < tmpMinSubResult):
tmpMinSubResult = abs(i - j - minSubNum)
subKey = i_key
minuendKey = j_key
if (subFlag == True):
return (subKey, minuendKey)
else:
return (minuendKey, subKey)
if __name__ == '__main__':
aa = range(20);
bb = [random.randint(0, 100) for i in aa]
bb.sort(reverse=True)
print aa
print bb
leftArray = []
rightArray = []
while (len(bb)):
tmpNumArray = bb[0:2]
bb = bb[2:]
if (sum(leftArray)