程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-12(32)

2022-01(15)

传闻中的华为Python面试题(原创)

发布于2019-07-16 19:43     阅读(5118)     评论(0)     点赞(49)     收藏(71)


原题:
有两个序列a,b,大小都为n,序列元素的值任意整形数,无序;
要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小

限时十分钟以内

 

尝试解答,coding和debug共用了约1个小时,呵呵,去不了华为了。
获取最小差的函数,还可以优化,现在的时间复杂度是n×n,估计可以优化到n×lg(n)

 

网上有一种解答方法,认为最小值是负数,排序之后,截成两段,小数序列-大数序列即可。难道,难道,这才是本题十分钟解出的奥义?!

我的代码如下,算法很简单(我的算法不对,请列位看官参考评论中张三的):

 

 

'''
Created on 2010-6-21

@author: maodouzi
'''
import random

def getMinSubKeys(leftArray, rightArray):
    if (sum(leftArray) > sum(rightArray)):
        subArray = leftArray
        minuendArray = rightArray
        subFlag = True
    elif (sum(leftArray) < sum(rightArray)):
        subArray = rightArray
        minuendArray = leftArray
        subFlag = False
    else:
        return None
    
    minSubNum = (sum(subArray) - sum(minuendArray)) / 2.0
    
    tmpMinSubResult = sum(subArray)
    subKey = 0
    minuendKey = 0
    for i_key, i in enumerate(subArray):
        for j_key, j in enumerate(minuendArray):
            if (abs(i - j - minSubNum) < tmpMinSubResult):
                tmpMinSubResult = abs(i - j - minSubNum)
                subKey = i_key
                minuendKey = j_key
                
    if (subFlag == True):
        return (subKey, minuendKey)
    else:
        return (minuendKey, subKey)

if __name__ == '__main__':
    aa = range(20);
    bb = [random.randint(0, 100) for i in aa]
    bb.sort(reverse=True)
    print aa
    print bb
    
    leftArray = []
    rightArray = []
    while (len(bb)):
        tmpNumArray = bb[0:2]
        bb = bb[2:]
        
        if (sum(leftArray) <= sum(rightArray)):
            leftArray.append(tmpNumArray[0])
            rightArray.append(tmpNumArray[1])
        else :
            leftArray.append(tmpNumArray[1])
            rightArray.append(tmpNumArray[0])
            
        leftArray.sort()
        rightArray.sort()
        tmpKeyArray = getMinSubKeys(leftArray, rightArray)
        if (tmpKeyArray == None):
            continue
        else:
            orgSubNum = abs(sum(leftArray) - sum(rightArray));
            newSubNum = abs(orgSubNum + (rightArray[tmpKeyArray[1]] - leftArray[tmpKeyArray[0]]) * 2)
            if (newSubNum < orgSubNum):
                tmpNum = leftArray[tmpKeyArray[0]]
                leftArray[tmpKeyArray[0]] = rightArray[tmpKeyArray[1]]
                rightArray[tmpKeyArray[1]] = tmpNum
        
        leftArray.sort()
        rightArray.sort()
    
    print leftArray, sum(leftArray)
    print rightArray, sum(rightArray)
    
    print "The subNum is: %d" % abs(sum(leftArray) - sum(rightArray))

 

 

输出结果如下:

 

 

[93, 91, 90, 82, 81, 74, 74, 74, 74, 68, 60, 57, 49, 48, 48, 45, 36, 35, 29, 22]
[22, 36, 48, 48, 60, 68, 74, 81, 82, 93] 612
[29, 35, 45, 49, 57, 74, 74, 74, 90, 91] 618
The subNum is: 6

 



所属网站分类: 技术文章 > 博客

作者:把镜子打碎

链接:https://www.pythonheidong.com/blog/article/1710/4914a44473a7781e163e/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

49 0
收藏该文
已收藏

评论内容:(最多支持255个字符)