[问题] 算法问题 cutekid PTT批踢踢实业坊

楼主: cutekid (可爱小孩子) 2014-08-01 16:48:20

N 个整数(不重复)
N1,N2,N3,N4...Nn
针对每个 Ni
求 Ni+1,Ni+2,Ni+3...Nn 当中小于 Ni 的值有几个
例:
Input : 4,3,1,5,2
Output: 3,2,0,1,0
请问这个有比 O(n^2) 更好的算法吗
谢谢 :)

作者: yr (Sooner Born Sooner Bred) 2014-08-01 16:59:00

不是排个序就好了？ O(n log n)理解错问题，请无视 XD

作者: yvb 2014-08-01 17:22:00

楼上的理解其实也没错, 稍微转化一下, 即可适用此题 :)

楼主: cutekid (可爱小孩子) 2014-08-01 17:27:00

可以请 yvb 大开示一下吗 :)

作者: flere (人间失格) 2014-08-01 18:48:00

用线段树可以做到O(n log n)..感觉有别的方法OAO

作者: dreamoon (千古悲情人物) 2014-08-01 18:56:00

http://ppt.cc/DEO1这是相关文章，搜寻逆序数对+树状数组应该可以搜到很多东西

作者: lNishan (紫小霓) 2014-08-01 19:04:00

推月神 <(_ _)>

作者: FRAXIS (喔喔) 2014-08-01 19:54:00

如果是单纯算inversion 用线段树会比较快嘛？

作者: johnathan717 (柏良) 2014-08-01 22:49:00

如果mergesort排序可以一边排，一边数inversions

作者: FRAXIS (喔喔) 2014-08-02 07:49:00

我也是这样觉得使用线段数有什么好处嘛？

作者: fenzhang (分帐) 2014-08-03 00:18:00

线段树可以处理动态情况，例如每次修改某个数字

作者: FRAXIS (喔喔) 2014-08-03 20:37:00

那当问题是静态的时候线段树应该就没有优势了吧?

作者: DJWS (...) 2014-08-03 20:52:00

时间复杂度都一样有没有优势就看实作功力囉

作者: suhorng ( ) 2014-08-04 13:38:00

可能没有. 当然比赛时线段树可能有模板, 可以直接套.但他常数也可能比较大啦只不过是 trade-off

作者: trail0721 (大肚鱼) 2014-08-20 13:29:00

Ni+1,Ni+2,Ni+3...Nn=>有序递增, i.e; 3,4,5,6,7,8,9..输入 8 => 输出 (8-3) = 5哈~~~~ 轻松一下...

作者: DJWS (...) 2014-10-03 09:50:00

归并树 / 划分树

继续阅读