algorithm:huawei-interview

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

@@ 行 1: / 行 1: @@
+====== 华为面试题 ======
+===== 求两序列的和最小差值序列 =====
+==== 题目 ====
+有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
+要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
+==== 算法 ====
+. 将两序列合并为一个序列，并排序，为序列Source
+. 拿出最大元素Big，次大的元素Small
+. 在余下的序列S[:-2]进行平分，得到序列max，min
+. 将Small加到max序列，将Big加大min序列，重新计算新序列和，和大的为max，小的为min。
+==== python实现代码 ====
+<code python>
+def mean( sorted_list ):
+    if not sorted_list:
+        return (([],[]))
+    big = sorted_list[-1]
+    small = sorted_list[-2]
+    big_list, small_list = mean(sorted_list[:-2])
+    big_list.append(small)
+    small_list.append(big)
+    big_list_sum = sum(big_list)
+    small_list_sum = sum(small_list)
+    if big_list_sum > small_list_sum:
+        return ( (big_list, small_list))
+    else:
+        return (( small_list, big_list))
+tests = [   [1,2,3,4,5,6,700,800],
+            [10001,10000,100,90,50,1],
+            range(1, 11),
+            [12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]
+            ]
+for l in tests:
+    l.sort()
+    print
+    print "Source List:\t", l
+    l1,l2 = mean(l)
+    print "Result List:\t", l1, l2
+    print "Distance:\t", abs(sum(l1)-sum(l2))
+    print '-*'*40
+</code>
+==== 输出结果 ====
+<file>
+Source List:    [1, 2, 3, 4, 5, 6, 700, 800]
+Result List:    [1, 4, 5, 800] [2, 3, 6, 700]
+Distance:       99
+-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
+Source List:    [1, 50, 90, 100, 10000, 10001]
+Result List:    [50, 90, 10000] [1, 100, 10001]
+Distance:       38
+-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
+Source List:    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
+Result List:    [2, 3, 6, 7, 10] [1, 4, 5, 8, 9]
+Distance:       1
+-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
+Source List:    [1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312]
+Result List:    [1, 3, 29, 232, 12311] [1, 2, 30, 210, 12312]
+Distance:       21
+-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
+</file>

algorithm/huawei-interview.txt · 最后更改: 2010/06/02 01:18 (外部编辑)