一亩三分地论坛

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

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

[算法题] 算法题求救

[复制链接] |试试Instant~ |关注本帖
qieguo 发表于 2015-8-2 20:53:13 | 显示全部楼层 |阅读模式

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

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

x
大家好,我今天在网上看到一道题,挺简单的,但是我只能找到最简单的O(n^2)的解法,我想这道题应该不止于这样的时间复杂度,想问问各位大神,能否有更好的解法呢?

题目是给出一组int 类型的数组,现有一个条件要求某个数大于位于其之后的某个数,则这两个数可以构成一个 pair,那么这样的 pair 有多少对呢?

我能想到的就是两次遍历,暴力去求。
stellari 发表于 2015-8-2 21:40:21 | 显示全部楼层
你可以建立一个BST,其中的每一个节点都记录了以该节点为根的子树中的结点个数。对每一个数字A【i】,在BST中寻找第一个大于A【i】的数字,然后将A【i】其插入BST中。在BST中查找需要O(logN)时间,查找的同时就可以顺便数出大于A【i】的数字个数。因此该算法的复杂度是O(NLogN)

另一个方法是:对数组用mergesort排序。在merge过程数出左右两段之间的逆序pair。这种情况下的逆序pair数可以在O(N)内做到。所以,总时间复杂度同样是O(NlogN)
回复 支持 1 反对 0

使用道具 举报

pyx115 发表于 2015-8-2 21:41:39 | 显示全部楼层
本帖最后由 pyx115 于 2015-8-2 21:44 编辑

汗,没看仔细,刚回复了个不合题意的答案,我再想想
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-2 23:02:25 | 显示全部楼层
计算逆序对.
经典算法, BIT 或者叫Fenwick tree
回复 支持 反对

使用道具 举报

jackjiang2 发表于 2015-8-2 23:11:30 | 显示全部楼层
不知道 可不可以用归并的思想来做
回复 支持 反对

使用道具 举报

 楼主| qieguo 发表于 2015-8-2 23:38:31 | 显示全部楼层
谢谢各位大神
回复 支持 反对

使用道具 举报

 楼主| qieguo 发表于 2015-8-2 23:38:44 | 显示全部楼层
谢谢各位大神
回复 支持 反对

使用道具 举报

JeffreyXIE 发表于 2015-8-3 13:28:44 | 显示全部楼层
感觉这个就是coursera standord algorithm编程题的第一题啊,课上的方法是用mergesort来count, 那running time就应该是nlog(n)。
小弟才准备转cs,门外汉,如有说错求轻拍。
回复 支持 反对

使用道具 举报

jackjiang2 发表于 2015-8-3 20:46:22 | 显示全部楼层
JeffreyXIE 发表于 2015-8-3 00:28
感觉这个就是coursera standord algorithm编程题的第一题啊,课上的方法是用mergesort来count, 那running t ...

应该木有错,我以前在国内的一个blog上面读过相关的,貌似这还是一道M家的面试题,对了大兄弟,求你同学在中兴的遭遇啊 0.0,
回复 支持 反对

使用道具 举报

JeffreyXIE 发表于 2015-8-4 09:53:56 | 显示全部楼层
jackjiang2 发表于 2015-8-3 20:46
应该木有错,我以前在国内的一个blog上面读过相关的,貌似这还是一道M家的面试题,对了大兄弟,求你同学 ...

具体我也不是很清楚,他就说太辛苦,死加班,公司本土化差,工资又低。好像他已经跳到别的公司了。
回复 支持 反对

使用道具 举报

jackjiang2 发表于 2015-8-4 09:56:20 | 显示全部楼层
JeffreyXIE 发表于 2015-8-3 20:53
具体我也不是很清楚,他就说太辛苦,死加班,公司本土化差,工资又低。好像他已经跳到别的公司了。

工资也太低了    10块钱一小时  妈的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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