作者cutekid (可爱小孩子)
看板Prob_Solve
标题[问题] 演算法问题
时间Fri Aug 1 16:48:20 2014
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) 更好的算法吗
谢谢 :)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 210.61.233.210
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1406882903.A.8DD.html
1F：→ yr:不是排个序就好了？ O(n log n) 08/01 16:59
2F：→ yr:理解错问题，请无视 XD 08/01 17:05
3F：推 yvb:楼上的理解其实也没错, 稍微转化一下, 即可适用此题 :) 08/01 17:22
4F：→ cutekid:可以请 yvb 大开示一下吗 :) 08/01 17:27
5F：推 flere:用线段树可以做到O(n log n)..感觉有别的方法OAO 08/01 18:48
7F：推 dreamoon:这是相关文章，搜寻 逆序数对+树状数组应该可以搜到很多 08/01 18:59
8F：→ dreamoon:东西 08/01 18:59
9F：推 lNishan:推月神 <(_ _)> 08/01 19:04
10F：推 FRAXIS:如果是单纯算inversion 用线段树会比较快嘛？ 08/01 19:54
11F：推 johnathan717:如果mergesort排序可以一边排，一边数inversions 08/01 22:49
12F：推 FRAXIS:我也是这样觉得 使用线段数有什麽好处嘛？ 08/02 07:49
13F：推 fenzhang:线段树可以处理动态情况，例如每次修改某个数字 08/03 00:18
14F：推 FRAXIS:那当问题是静态的时候 线段树应该就没有优势了吧? 08/03 20:37
15F：推 DJWS:时间复杂度都一样 有没有优势就看实作功力罗 08/03 20:52
16F：推 suhorng:可能没有. 当然比赛时线段树可能有模板, 可以直接套. 08/04 13:38
17F：→ suhorng:但他常数也可能比较大啦 只不过是 trade-off 08/04 13:38
18F：推 trail0721: Ni+1,Ni+2,Ni+3...Nn=>有序递增, i.e; 3,4,5,6,7,8,9.. 08/20 13:29
19F：→ trail0721: 输入 8 => 输出 (8-3) = 5 08/20 13:30
20F：→ trail0721: 哈~~~~ 轻松一下... 08/20 13:30
21F：推 DJWS: 归并树 / 划分树 10/03 09:50