一亩三分地论坛

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

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

[算法题] binary search一般都是对index二分,那什么时候对数组的数据本身二分?

[复制链接] |试试Instant~ |关注本帖
littlebearull 发表于 2016-8-20 06:37:18 | 显示全部楼层 |阅读模式

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

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

x
比如leetcode 378的binary search解法中,就是对数组的数据本身进行二分。我的问题是,这道题可以对index二分吗?如果可以,怎么做的呢?谢谢小伙伴们的回复!
chaosMonkey 发表于 2016-9-26 12:20:17 | 显示全部楼层
这个题二分的解法是什么样的?我是用杨氏矩阵的解法
回复 支持 反对

使用道具 举报

阿童木 发表于 2016-10-5 02:12:08 | 显示全部楼层
本帖最后由 阿童木 于 2016-10-4 12:52 编辑

我是初学者,但看了一些discuss里的post也结合了自己上课学的东西,用的是min heap的方法(时间复杂度O(n+klogn),n是矩阵的长度或宽度),你可以看一下我总结的这个https://github.com/TongZhangUSC/ ... blob/master/Heap.md,希望对你有用。
回复 支持 反对

使用道具 举报

 楼主| littlebearull 发表于 2016-10-16 06:28:36 | 显示全部楼层
阿童木 发表于 2016-10-5 02:12
我是初学者,但看了一些discuss里的post也结合了自己上课学的东西,用的是min heap的方法(时间复杂度O(n+k ...

谢谢你呀~ 是的,你的方法挺好的,也很容易理解,:)
回复 支持 反对

使用道具 举报

 楼主| littlebearull 发表于 2016-10-16 06:29:29 | 显示全部楼层
chaosMonkey 发表于 2016-9-26 12:20
这个题二分的解法是什么样的?我是用杨氏矩阵的解法

不好意思,才看到。就是把矩阵第一个元素和最后一个元素分别作为two pointer的起点和终点,然后做二分查找。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 19:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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