[問題] 演算法問題 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

归并树 / 划分树

繼續閱讀