免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 28902 | 回复: 67

[算法] 搜狐2012牛逼笔试题,至今无思路,求牛人指点 [复制链接]

论坛徽章:
0
发表于 2011-10-06 21:23 |显示全部楼层
有N个正实数(注意是实数,大小升序排列) x1 , x2 ...  xN,另有一个实数M。
需要选出若干个x,使这几个x的和与 M 最接近。
请描述实现算法,并指出算法复杂度

论坛徽章:
1
天蝎座
日期:2013-12-06 18:23:58
发表于 2011-10-06 21:43 |显示全部楼层
可以借用下数组最大子和问题吧,O(n) 可以搞定

论坛徽章:
0
发表于 2011-10-06 21:54 |显示全部楼层
我觉得还是bitmap解决好点。

论坛徽章:
0
发表于 2011-10-06 23:11 |显示全部楼层
这个,直观的方法是用穷举法,可以用一个变量来表示那几个数的结果与选定的结果的差值,只要发现当前遍历的差大于那个变量里存的差值,就提前结束便利。
也就是说,虽然用的是穷举,但是由于能够做到提前剪枝,所以算法复杂度也不会太大。
说白了,就是使用排列,随时计算排列的值和指定的值的差,因为那几个X是排序的,所以可以预测排列后面的组合和制定值的差的趋势,从而可以做到剪枝

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2011-10-07 00:47 |显示全部楼层
穷举,时间复杂度指数级

论坛徽章:
0
发表于 2011-10-07 12:47 |显示全部楼层
《编程珠玑第二版》上有一个问题与此极为类似。
记得算法复杂度是N。

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2011-10-07 17:54 |显示全部楼层
回复 1# snowboy9859


    这个比背包问题更复杂, 起码和背包问题一个难度, 网上搜索一下

论坛徽章:
0
发表于 2011-10-07 19:14 |显示全部楼层
楼主的问题正好是kNN算法的一部分,就是寻找k个最近邻。上网找下这方面的实现就好

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2011-10-07 20:24 |显示全部楼层
别想了
指数级别
没更好的算法

论坛徽章:
1
天秤座
日期:2014-04-27 07:42:20
发表于 2011-10-08 08:20 |显示全部楼层
虽然是有序的,但你不遍历怎么知道M在那个位置呢?
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP