python小算法(二)

有两个序列a,b,大小都为n,序列元素的值任意整形数,无序;

要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。(华为面试)

def diff(sorted_list, length):
if not sorted_list:
return (([],[]))
last = sorted_list[-1]
big_list, small_list = diff(sorted_list[:-1],length)
big_list_sum = sum(big_list)
small_list_sum = sum(small_list)
if big_list_sum > small_list_sum:
if len(small_list) >= length:
big_list.append(last)
else:
small_list.append(last)
return ((big_list, small_list))
else:
if len(big_list) >= length:
small_list.append(last)
else:
big_list.append(last)
return ((small_list, big_list)) def deal(one, two):
for i in xrange(len(one)-1,-1,-1):
for j in xrange(len(two)-1,-1,-1):
d = abs(sum(one) - sum(two))
if 0<= one[i] - two[j] <=d:
one[i], two[j] = two[j], one[i]
return ((one, two)) a = [1,3,5,7,99,100,200]
b = [2,4,6,88,10,9,233]
length = len(a)
a.extend(b)
p = sorted(a,reverse=True)
one, two = diff(p, length)
one, two = deal(one, two)
print one
print two
print sum(one), sum(two), sum(one) - sum(two)

  

  

上一篇:POJ 1160 题解


下一篇:获得当前屏幕的CGRect