有兩個序列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 oneprint twoprint sum(one), sum(two), sum(one) - sum(two)
新聞熱點
疑難解答