一亩三分地论坛

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

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

[算法题] 请教一个二分法的题

[复制链接] |试试Instant~ |关注本帖
comicrudy 发表于 2016-5-30 12:34:57 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 comicrudy 于 2016-5-31 00:03 编辑

之前google面经里有的关于majority element的题,就是一个排序数组有n个值,求所有出现次数等于或者超过n / k的值。
比如[1 1 2 2 2 2 3 4 5 5 5 5]
k = 3
return [2,5]

知道是应该用binary search做,但是具体逻辑搞不太明白啊?

jy_121 发表于 2016-5-30 12:54:15 | 显示全部楼层
根据题意,满足条件的点只可能出现在n/k,2n/k....,n  对这几个点用二分法求range,看看个数是否大于n/k.
回复 支持 反对

使用道具 举报

 楼主| comicrudy 发表于 2016-5-30 13:48:17 | 显示全部楼层
jy_121 发表于 2016-5-30 12:54
根据题意,满足条件的点只可能出现在n/k,2n/k....,n  对这几个点用二分法求range,看看个数是否大于n/k.

能具体讲一讲怎么求range么?需要先比较n/k, 2n/k么?
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-30 14:04:14 | 显示全部楼层
comicrudy 发表于 2016-5-30 13:48
能具体讲一讲怎么求range么?需要先比较n/k, 2n/k么?

你去做下leetcode的search for range就知道了
回复 支持 反对

使用道具 举报

 楼主| comicrudy 发表于 2016-5-30 15:04:10 | 显示全部楼层
jy_121 发表于 2016-5-30 14:04
你去做下leetcode的search for range就知道了

应该可以剪枝吧?不需要对每一个值都找完range。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-30 23:23:16 | 显示全部楼层
维护一个K window,对这个K window 内的数求 one majority element?
回复 支持 反对

使用道具 举报

南方Giraffe 发表于 2016-5-31 01:07:01 | 显示全部楼层
不懂用binary search怎么做 不过lc easy里面有道差不多的 不过k固定是2 我直接遍历数组存hashmap里了....虽然很慢...等大神回复....
回复 支持 反对

使用道具 举报

南方Giraffe 发表于 2016-5-31 01:12:34 | 显示全部楼层
一个想法是:因为这个数组是排了序的 所以符合条件的数只可能在n/k n/2k...的位置上 因此只需要把这些位置的数前后出现次数加起来...
回复 支持 反对

使用道具 举报

adrianliu729 发表于 2016-5-31 16:27:39 | 显示全部楼层
首先,target 只能是 n / k, 2n/k, ... ,(n - k) / k, 然后你对每一个target进行一次二分查找就好了,二分查找就是找最左边是这个数的(比如index1),最右边是这个数的(index2), 然后你用index2 - index1 看是不是符合题目要求了,把所有符合要求的都放在结果里面就好了。复杂度应该是 k*logN 吧?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 14:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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