📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2380| 回复: 10
跳转到指定楼层
上一主题 下一主题
收起左侧

算法题求救

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

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

我能想到的就是两次遍历,暴力去求。

上一篇:求助求助:interval schedule, n room for most number of meetings with priority
下一篇:求给定数等于最少的几个完全平方数之和
推荐
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)
回复

使用道具 举报

🔗
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家的面试题,对了大兄弟,求你同学 ...

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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