免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › 搜狐2012牛逼笔试题，至今无思路，求牛人指点
1234567下一页
最近访问板块 发新帖
查看: 28750 | 回复: 67
打印 上一主题 下一主题

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

snowboy9859

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2011-10-06 21:23 |只看该作者 |倒序浏览
有N个正实数(注意是实数，大小升序排列) x1 , x2 ...  xN，另有一个实数M。
需要选出若干个x，使这几个x的和与 M 最接近。
请描述实现算法，并指出算法复杂度
crazyhadoop

论坛徽章:
1
天蝎座 日期:2013-12-06 18:23:58
2楼 [报告]
发表于 2011-10-06 21:43 |只看该作者
可以借用下数组最大子和问题吧，O(n) 可以搞定
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
shitou254

论坛徽章:
0
3楼 [报告]
发表于 2011-10-06 21:54 |只看该作者
我觉得还是bitmap解决好点。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
unistd

论坛徽章:
0
4楼 [报告]
发表于 2011-10-06 23:11 |只看该作者
这个，直观的方法是用穷举法，可以用一个变量来表示那几个数的结果与选定的结果的差值，只要发现当前遍历的差大于那个变量里存的差值，就提前结束便利。
也就是说，虽然用的是穷举，但是由于能够做到提前剪枝，所以算法复杂度也不会太大。
说白了，就是使用排列，随时计算排列的值和指定的值的差，因为那几个X是排序的，所以可以预测排列后面的组合和制定值的差的趋势，从而可以做到剪枝
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
cjaizss

论坛徽章:
3
2015年迎新春徽章 日期:2015-03-04 09:56:11数据库技术版块每日发帖之星 日期:2016-08-03 06:20:00数据库技术版块每日发帖之星 日期:2016-08-04 06:20:00
5楼 [报告]
发表于 2011-10-07 00:47 |只看该作者
穷举,时间复杂度指数级
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
jtkk

论坛徽章:
0
6楼 [报告]
发表于 2011-10-07 12:47 |只看该作者
《编程珠玑第二版》上有一个问题与此极为类似。
记得算法复杂度是N。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
goldenfort

论坛徽章:
1
2015年辞旧岁徽章 日期:2015-03-03 16:54:15
7楼 [报告]
发表于 2011-10-07 17:54 |只看该作者
回复 1# snowboy9859


    这个比背包问题更复杂， 起码和背包问题一个难度， 网上搜索一下
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
jeung

论坛徽章:
0
8楼 [报告]
发表于 2011-10-07 19:14 |只看该作者
楼主的问题正好是kNN算法的一部分，就是寻找k个最近邻。上网找下这方面的实现就好
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
cjaizss

论坛徽章:
3
2015年迎新春徽章 日期:2015-03-04 09:56:11数据库技术版块每日发帖之星 日期:2016-08-03 06:20:00数据库技术版块每日发帖之星 日期:2016-08-04 06:20:00
9楼 [报告]
发表于 2011-10-07 20:24 |只看该作者
别想了
指数级别
没更好的算法
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
A.com

论坛徽章:
1
天秤座 日期:2014-04-27 07:42:20
10楼 [报告]
发表于 2011-10-08 08:20 |只看该作者
虽然是有序的，但你不遍历怎么知道M在那个位置呢？
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
1234567下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP