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

shhgs

很难。10分钟肯定不够。我想算法得20分钟。真正出代码得一个小时。

顺便说一句，针对这道题，所有“投机取巧”的算法，我都表示怀疑。因为你们没有办法用数学证明你们的算法是可靠的。

[ 本帖最后由 shhgs 于 2010-1-29 23:52 编辑 ]

lxguidu

看来我的能力不行啊，各位都是高手，领教了！

shhgs

其实这道题还真不是考你们算法的。这是考你们的数据结构的。照着题目的意思，用swap元素的方式调整。要说算法，其实就是设计一个停止的条件。就是判断当前情况下，没有可调整的元素了。

1. 
   
2.     a1          a2          a3      a4 ...
   
3. b1  (1,1),m1   (1,2),m2     ...
   
4. b2  ...
   
5. b3  ...
   
6. .
   
7. .
   
8. .
   

复制代码

很明显，这是一个dict，键就是序列a和b的下标（tuple），值就是他们的差。

这里的停止条件是，n = sum(a) - sum(b) 和这个dict里面的所有值的比较（假设某个值为m）。有两个条件
1. m 和 n 符号相同（同正或同负）
2. ｜m - n｜ < n
然后，选 |m - n| 最小的那个m，找出其对应的a和b的下标，swap两个元素。

[ 本帖最后由 shhgs 于 2010-1-30 06:22 编辑 ]

nankai559

以上所有非指数级算法都不对，因为此问题至少是NP-Complete.

理由:
将两个数组合并后从小到大排序，然后a'取前一半小值，b'取后一半大值。
这里假设一种简化情况，就是我们只需交换a'，b'中相同位置的元素就可获得最优解(实际情况要更加复杂)。
然后我们将数组C设为b'-a'，是一组正整数; 设正整数T为(sum(b')-sum(a'))/2。现在问题变为:

1. 一组正整数集合C，目标正整数T, 求C中的一个子集使得此子集的和在不超过T的情况下越大越好，
或
2. 一组正整数集合C，目标正整数T, 求C中的一个子集使得此子集的和在不小于T的情况下越小越好。

问题1被称为子集和问题(subset sum problem)，可以看做是背包问题的一个特例。此问题是NP-Complete的。

两个关于subset sum problem的链接:
http://www.cs.dartmouth.edu/~ac/ ... /nanda-scribe-3.pdf
http://en.wikipedia.org/wiki/Subset_sum_problem

因为本问题的一个简化情况都是NP-Complete的，所以这个问题本身至少是NP-Complete的。

Kabie

1. def gotans(a,b):
   
2.         c=sorted(a+b,reverse=(sum(a+b)>0))
   
3.         S=sum(c)
   
4.         s=abs(S)
   
5.         S=S/2
   
6.         for i in itertools.combinations(c,len(a)):
   
7.                 tmp = abs(sum(i)-S)
   
8.                 if tmp<s:
   
9.                         s=tmp
   
10.                         print(s,sum(i),i)
    
11.                         if tmp==0 or tmp==0.5:
    
12.                                 break

复制代码

...10分钟也只好先穷举了……效率非常低。。。。

litanhe

1. 合并两个数组
2. 数组排序，
3. 如果最小数是负数，则所有元素先加上其绝对值
4. 分配序列：
   序列1和序列2默认sum为零
    分配序列到序列1，直到求和大于序列2，然后其余数分配到序列2，直到序列2求和和大于序列1
  终止：某个序列数目达到n，未分配序列分配到另一序列组
这样得到的两个序列求和差值是否最小？

aoma

我的想法
数组从大到小排序得到数组A(A1,A2,A3,...A2n)
建两个新数组B,C,先从A取最大的两个元素,分别给B,C,到底sum(B)和sum(C)谁大不重要,如果B大则C取第三个,如果C大则B取第三个,第四个元素取最后的元素A2, B和C得到两个元素后,开始计算sum,谁小取第A4个元素,依次类推

fisherjams

给你个思路八

两个序列合并求和并求平均值avg
min=avg-avg*n/2
max=avg+avg*n/2

最后a序列为>=min且<=max的数，b序列为其他

用a,b交换实现上述结果

fisherjams

在进一步

先对ab分别排序,a从大向小，b从小向大

a和b 在min和max之间有交集，对交集互换，过avg点后交换方向相反