一亩三分地论坛

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

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

一道coding题

[复制链接] |试试Instant~ |关注本帖
Lilian1109 发表于 2016-7-19 04:06:39 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Bloomberg - 内推 - Onsite |Other其他

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

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

x
遇到这样一道题, 有一个数列, 比如说[120, 200, 400, 300, 500], 要求输出在当前index之后的比当前数值大的数的个数, 对于例子里的数组。 就是[4, 3, 1, 1, 0]。
先看错了题, 搞了一通发觉搞错了方向。 怎么做能比O(n^2)简单。 这是哪里的原题吗?


评分

1

查看全部评分

damonment 发表于 2016-7-19 06:32:28 | 显示全部楼层
上来就面这么难的。。
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2016-7-19 04:14:12 | 显示全部楼层
https://leetcode.com/problems/count-of-smaller-numbers-after-self/

BIT
回复 支持 反对

使用道具 举报

 楼主| Lilian1109 发表于 2016-7-19 04:38:44 来自手机 | 显示全部楼层
好吧,题刷的少 估计肯定挂了
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-7-19 08:11:13 | 显示全部楼层
同意。。这题真不容易,可能如果楼主讲了BST解法也能过吧,MergeSort忒难想了。
回复 支持 反对

使用道具 举报

phantom 发表于 2016-7-19 08:26:40 | 显示全部楼层
就相当于求数组里的逆序数的对数。。
非常经典的Divide and Conquer的解法,就和Merge Sort写法类似。。。可以到O(nlog(n))的复杂度
回复 支持 反对

使用道具 举报

b00901192 发表于 2016-7-19 20:30:31 | 显示全部楼层
有點類似 merge sort 的方式,每次都從中間將數列切成兩塊,切到不能再切時,開始 merge, 將前半段每個元素與後半段比較,只要小於就 + 1, 做完就得解了。
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-7-21 06:15:25 | 显示全部楼层
自己构建一棵BST 就可以了 自己想的方法 好像还没有看到人用过
回复 支持 反对

使用道具 举报

emmonenirvana 发表于 2016-7-24 13:07:55 | 显示全部楼层
目测是一道很经典的segment tree的题
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-7-24 13:40:24 | 显示全部楼层
类似 https://leetcode.com/problems/count-of-smaller-numbers-after-self/
可以线段树做的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 03:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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