一道分治算法问题

2015-04-08 21:17:46 +08:00

xingo

你们敢相信我这算法老师也不懂？？？我感觉他连题目都没看懂。。。。。他以为是一个进去找一个出来。。。那SELECT算法时间复杂度已经是O(n)了，还需要啥O(n logr)...
谷歌了也没找到。。。。。。。

2944 次点击

所在节点

24 条回复

Angdo

2015-04-09 19:07:23 +08:00

@xingo 前面不小心顺序错了，select里取k中值，拆分数组k

lvfujun

2015-04-09 21:08:10 +08:00

@xingo 楼猪真是用心良苦啊.为了让广大屌丝程序猿们活动下脖子......建议第二张图再顺时针旋转180度.

slayer

2015-04-10 06:46:13 +08:00

这题大概懂了，但是29题是怎么回事？SELECT选出了第k小元素X，那么前面的不都是比X还小的元素，直接都返回就可以了吧，还是O(n)都复杂度。

xingo

2015-04-10 06:50:43 +08:00

@slayer 29题不是和30差不多嘛，top k

第 2 页／共 2 页

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.