首页 > 代码库 > 传说中的华为Python笔试题——两等长整数序列互换元素，序列和的差值最小(修正)
传说中的华为Python笔试题——两等长整数序列互换元素，序列和的差值最小(修正)
有两个序列a,b，大小都为n,序列元素的值任意整形数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
1. 将两序列合并为一个序列，并排序，得到sourceList
2. 拿出最大元素Big，次大的元素Small
3. 在余下的序列S[:-2]进行平分，得到序列max，min
4. 将Small加到max序列，将Big加大min序列，重新计算新序列和，和大的为max，小的为min。
如下，提供递归版本和迭代版本的解体思路：
#!/usr/bin/env python# -*- coding: utf-8 -*-########################################################################## File Name: minDistance.py# Author: lpqiu# mail: qlp_1018@126.com# Created Time: 2014年10月27日 星期一 05时19分45秒########################################################################## recusive versiondef minDist(sortedList): if not sortedList: return ([], []) large = sortedList[-1] secondLarge = sortedList[-2] largeList, smallList = minDist(sortedList[:-2]) largeList.append(secondLarge) smallList.append(large) #print(‘LargeList:‘, largeList, ‘SmallList‘, smallList) if sum(largeList) > sum(smallList): return (largeList, smallList) else: return (smallList, largeList)# iteriation versiondef minDistIterVer(sortedList): largeList, smallList = [], [] for i in range(0, len(sortedList), 2): if sum(largeList) > sum(smallList): largeList.append(sortedList[i]) smallList.append(sortedList[i + 1]) else: largeList.append(sortedList[i + 1]) smallList.append(sortedList[i]) if sum(largeList) > sum(smallList): return (largeList, smallList) else: return (smallList, largeList)def testMain(listA, listB): # len(listA) == len(listB) = n print("Sorted List: ", sorted(listA + listB)) largeList, smallList = minDist(sorted(listA + listB)) print(largeList, smallList, "distance: ", sum(largeList) - sum(smallList)) largeListIterVer, smallListIterVer = minDistIterVer(sorted(listA + listB)) print(largeListIterVer, smallListIterVer, "distance: ", sum(largeListIterVer) - sum(smallListIterVer))if __name__ == "__main__": listA = [1,-1,2,3,6,189]; listB = [2,3,4,6,7,123] testMain(listA, listB)传说中的华为Python笔试题——两等长整数序列互换元素，序列和的差值最小(修正)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。