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

wudi626

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

def FindTargetItem(diff,lst):
    for item in lst:
        if diff >= item:
            return lst.index(item)
        else:
            return -1

def Process(lstA,lstB):
    sumA = sum(lstA)
    sumB = sum(lstB)
   
    lstA.sort()
    lstB.sort()
   
    if sumA == sumB:
        return
    elif sumA > sumB:
        diff = sumA - sumB
        while diff >= 0:
            targetIndex = FindTargetItem(diff,lstA)
            if targetIndex == -1:
                return
            else:
                lstB.append(lstA.pop(targetIndex))
            sumA = sum(lstA)
            sumB = sum(lstB)
            diff = sumA - sumB
    else:
        diff = sumB - sumA
        while diff >= 0:
            targetIndex = FindTargetItem(diff,lstB)
            if targetIndex == -1:
                return
            else:
                lstA.append(lstB.pop(targetIndex))
            sumA = sum(lstA)
            sumB = sum(lstB)
            diff = sumB - sumA
    return

wudi626

原帖由 wudi626 于 2009-7-7 00:07 发表
# coding=gb2312
# 有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
# 要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。

def FindTargetItem(diff,lst):
    for ...

仔细看了下，这个算法不符合要求！

edgar

'''
Created on 2009-7-7

@author: Edgar
'''
def getDif(aList,bList):
    asum=0;
    bsum=0;
   
    for eachItemIndex in range(len(aList)):
        asum+=aList[eachItemIndex];
        bsum+=bList[eachItemIndex];
    return bsum-asum
def getMaxValue(aList,bList):
    aList.sort()
    aMax=aList[-1]
    bList.sort()
    bMax=bList[-1]
    if aMax<bMax:
        return bMax
    else:return aMax
   
def getTheProperPairs(aList,bList):
    theDif=getDif(aList, bList)
    theMinmum={"aList":0,"bList":0,"diff":getMaxValue(aList, bList)}
    for i in aList:
        for k in bList:
            theTempDif=2*(k-i)
            if theTempDif==theDif:
                theMinmum["diff"]=theTempDif
                theMinmum["aList"]=i
                theMinmum["bList"]=k
                return theMinmum
               
            if theMinmum["diff"]>abs(theTempDif-theDif):
                theMinmum["diff"]=abs(theTempDif-theDif)
                theMinmum["aList"]=i
                theMinmum["bList"]=k
   
    return theMinmum
是说只准交换一个吗？还是允许交换多个？交换位置有要求吗？
我这个程序是只准许一个，交换位置没有要求

sysengcn

为什么童鞋们总喜欢把简单问题复杂化呢？

其实只要想着让 sum(X) 和 sum(Y) 都往 ( sum(A) + sum(B) ) / 2 上靠不就完了吗。（这里假设 A, B 为源 list， X, Y 为所求的 list。）

因为只有当 sum(X) 和 sum(Y) 都最靠近那个中间点的时候，他们的差才会最小，对吧？


A = [1, 2, 700, 6]
B = [4, 3, 5, 800]
X = []
Y = []

pivot = ( sum(A) + sum(B) ) / 2

C = A + B
C.sort()

def next_one(sum) :
    if sum > pivot :
        return C.pop(0)
    else :
        return C.pop(-1)

while len(C) :
    if abs(sum(X) - pivot) > abs(sum(Y) - pivot) :
        # X is further away to pivot than Y, let X pick first
        X.append( next_one( sum(X) ) )
        Y.append( next_one( sum(Y) ) )
    else :
        # otherwise let Y pick first
        Y.append( next_one( sum(Y) ) )
        X.append( next_one( sum(X) ) )

print X
print Y
print abs(sum(X) - sum(Y))


[ 本帖最后由 sysengcn 于 2009-7-6 21:21 编辑 ]

edgar

sysengcn ,你这是不限次数的调换啊……

weizhe86

一，题目要求的是差值最小的方案，所以交换一对数据是不能实现的。
二，最后交换一对数据无法使差值减小，但是存在同时交换两对(还有更多对)数据可以减小差值的可能。

weizhe86

你这个问题，前边已经说过不对了，为什么还要发。

newman0708

1. 
   
2. 
   
3. def sumlist(list1):
   
4.     retsum=0
   
5.     for i in list1:
   
6.         retsum=retsum+i
   
7.     return retsum
   
8. 
   
9. 
   
10. def getminutegap(a1):
    
11.     minutegap=[]
    
12.     for i in xrange(len(a1)-1):
    
13.         val1=a1[i]
    
14.         val2=a1[i+1]
    
15.         gap=abs(val1-val2)
    
16.         minutegap.append(gap)
    
17.     return minutegap
    
18. 
    
19. def getmaxvalueindex(list1):
    
20.     maxv=max(list1)
    
21.     return list1.index(maxv)
    
22.    
    
23. def dividelist(a1,b1):
    
24.     a1.extend(b1)
    
25.     aaa=[]
    
26.     bbb=[]
    
27.     a1.sort()
    
28.     a1.reverse()
    
29.     print a1
    
30. 
    
31.     while(len(a1)>1):
    
32.         maxgapindex=getmaxvalueindex(getminutegap(a1))
    
33.         if sumlist(aaa)<=sumlist(bbb):
    
34.             aaa.append(a1[maxgapindex])
    
35.             bbb.append(a1[maxgapindex+1])
    
36.         else:
    
37.             aaa.append(a1[maxgapindex+1])
    
38.             bbb.append(a1[maxgapindex])            
    
39.         a1.remove(a1[maxgapindex])
    
40.         a1.remove(a1[maxgapindex])
    
41. 
    
42.     if (len(a1)>0) and (sumlist(aaa)<sumlist(bbb)):
    
43.         aaa.append(a1[0])
    
44. 
    
45.     aaasum=sumlist(aaa)
    
46.     bbbsum=sumlist(bbb)
    
47.     print aaa,aaasum,bbb,bbbsum,(sumlist(aaa)-sumlist(bbb))
    
48. 
    
49.         
    
50. 
    
51.    
    
52. #dividelist([1,2,5,3],[6,7,8,9,10])
    
53. #dividelist([300, 200],[ 150, 53, 12, 3])
    
54. 
    
55. 
    
56. 
    
57. 
    
58. dividelist([10001,10000],[100,90,50,1])
    
59. # 1001 1000 10 8 5 1
    
60. # 1001 8  5  =1014
    
61. # 1000 10 1  =1011
    
62. 
    
63. # 1001 10 1  =1012
    
64. # 1000 8  5  =1013
    
65. 
    
66. dividelist([101,100],[10, 8, 5, 1])
    
67. # 101 100 10 8 5 1
    
68. # 101 8  5  =113
    
69. # 100 10 1  =111
    
70. 
    
71. # 101 10 1  =112
    
72. # 100 8  5  =113
    
73. 
    
74. 
    

复制代码

luxyi

这题目就是考算法，跟 Python 没什么关系。

doctorwho

网上Google到的，觉得有道理，大家讨论一下，有更好的算法吗？
   
   求解思路：

    当前数组a和数组b的和之差为
    A = sum(a) - sum(b)

    a的第i个元素和b的第j个元素交换后，a和b的和之差为
    A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
           = sum(a) - sum(b) - 2 (a - b[j])
           = A - 2 (a - b[j])
    设x = a - b[j]

    |A| - |A'| = |A| - |A-2x|

    假设A > 0,

    当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,

    如果找不到在(0,A)之间的x，则当前的a和b就是答案。

    所以算法大概如下：

    在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。

[ 本帖最后由 doctorwho 于 2009-8-5 00:56 编辑 ]