一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 758|回复: 14
收起左侧

关于求kth largest的那道题

[复制链接] |试试Instant~ |关注本帖
雨做的云 发表于 2015-3-11 04:44:19 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 实习@Amazon - 内推 - 技术电面 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
就是关于find kth largest number 那个题,我看到地里的面经好多都提到careful with max heap and min heap.一直不太理解,难道不能直接用priorityqueue把数组里所有的元素全部add进去,如果是求k th min就poll k次,如果求k th max就poll (n-k)次吗? 大家讨论min heap和max heap 难道是说不让用priorityqueue,得用heap实现?之前看面经一直没理解,马上要面了,求大家指导
laonawuli 发表于 2015-3-11 05:44:42 | 显示全部楼层
不要直接全加进去,那样复杂度会很高,基本是NLogN的节奏。
你要维护一个大小为k的PQ,这样复杂度就是NLogK,这样LogK基本是常数级的了。

代码:
  1.     private int findKthLargest(int[] num, int k) {. visit 1point3acres.com for more.
  2.         if (num == null || num.length == 0) {
  3.             throw new IllegalArgumentException("num: should not be null or empty array.");
  4.         }
  5.         if (k < 1 || k > num.length) {
  6.             throw new IllegalArgumentException("k: out of bound.");
  7.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  8.         PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
  9.         for (int i : num) {
  10.             pq.add(i);
  11.             if (pq.size() > k) {
  12.                 pq.poll();
  13.             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14.         }. Waral 鍗氬鏈夋洿澶氭枃绔,

  15.         return pq.poll();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  16.     }
复制代码
回复 支持 1 反对 0

使用道具 举报

lijl900805 发表于 2015-3-11 04:57:58 | 显示全部楼层
建议看看priority queue的源码噜...
回复 支持 反对

使用道具 举报

 楼主| 雨做的云 发表于 2015-3-11 04:59:59 | 显示全部楼层
lijl900805 发表于 2015-3-11 04:57
建议看看priority queue的源码噜...
-google 1point3acres
priorityqueue是用heap实现的,我的意思是面的时候能不能直接用priorityque不用heanp噜。。。
回复 支持 反对

使用道具 举报

lijl900805 发表于 2015-3-11 05:07:59 | 显示全部楼层
雨做的云 发表于 2015-3-11 04:59
priorityqueue是用heap实现的,我的意思是面的时候能不能直接用priorityque不用heanp噜。。。
. from: 1point3acres.com/bbs
那有木有考虑过输入如果是stream的情况噜... 输入的数据量辣么大,poll出来也是要时间的噜... 祝好运
.1point3acres缃
补充内容 (2015-3-11 05:09):. visit 1point3acres.com for more.
加上你每次insert一个数据进去也是需要时间的噜...O(nlogn)和O(nlogk)哪个比较好噜...
回复 支持 反对

使用道具 举报

狂暴CNM地 发表于 2015-3-11 05:13:19 | 显示全部楼层
lijl900805 发表于 2015-3-11 05:07
那有木有考虑过输入如果是stream的情况噜... 输入的数据量辣么大,poll出来也是要时间的噜... 祝好运

补 ...

可以直接给一个collection O(n) 建堆吧 难道PRIORITY QUEUE用的不是O(N)的建堆算法?
回复 支持 反对

使用道具 举报

 楼主| 雨做的云 发表于 2015-3-11 05:28:24 | 显示全部楼层
lijl900805 发表于 2015-3-11 04:57
建议看看priority queue的源码噜...
. 1point3acres.com/bbs
大神贴贴代码噜
回复 支持 反对

使用道具 举报

surezero 发表于 2015-3-11 06:13:16 | 显示全部楼层
其实max min heap都能做 min heap是logk max是logn 一般情况下都是k < n 所以自然用min heap
. from: 1point3acres.com/bbs
不怎么写java 从没用过PQ 明天面试要是问到这个果断上伪代码。。过不过就是命了。。。
回复 支持 反对

使用道具 举报

 楼主| 雨做的云 发表于 2015-3-11 06:34:28 | 显示全部楼层
laonawuli 发表于 2015-3-11 05:44
不要直接全加进去,那样复杂度会很高,基本是NLogN的节奏。
你要维护一个大小为k的PQ,这样复杂度就是NLog ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
受教了!
回复 支持 反对

使用道具 举报

 楼主| 雨做的云 发表于 2015-3-11 06:34:44 | 显示全部楼层
laonawuli 发表于 2015-3-11 05:44. Waral 鍗氬鏈夋洿澶氭枃绔,
不要直接全加进去,那样复杂度会很高,基本是NLogN的节奏。
你要维护一个大小为k的PQ,这样复杂度就是NLog ...

受教了!字数!
回复 支持 反对

使用道具 举报

b232126660 发表于 2015-3-11 11:42:08 | 显示全部楼层
建议用 quickselect. 复杂度O(n)。而且代码很简单
回复 支持 反对

使用道具 举报

 楼主| 雨做的云 发表于 2015-3-11 11:58:41 | 显示全部楼层
b232126660 发表于 2015-3-11 11:42
建议用 quickselect. 复杂度O(n)。而且代码很简单

好的好的,谢啦,我两种都看一看
回复 支持 反对

使用道具 举报

swj817 发表于 2015-3-11 12:00:32 | 显示全部楼层
b232126660 发表于 2015-3-11 11:42. more info on 1point3acres.com
建议用 quickselect. 复杂度O(n)。而且代码很简单

如果输入是个stream的话 感觉还应该是楼上的方法
回复 支持 反对

使用道具 举报

funkyxie 发表于 2015-3-11 13:00:54 来自手机 | 显示全部楼层
直接建个k大小的堆,如果是数字就不用override comparator,如果是linkedlist 这种再override下,然后遍历一遍,最后取堆顶的,复杂度就nlogk啊
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-3-12 05:13:57 | 显示全部楼层
median of median?  worst O(n)..
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 18:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表