[問題] 演算法問題

看板Prob_Solve作者 (可愛小孩子)時間9年前 (2014/08/01 16:48), 編輯推噓14(14推 0噓 7→)
留言21則, 12人參與, 最新討論串4/8 (看更多)
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://www.ptt.cc/bbs/Prob_Solve/M.1406882903.A.8DD.html
→
08/01 16:59, , 1F
不是排個序就好了？ O(n log n)
08/01 16:59, 1F
→
08/01 17:05, , 2F
理解錯問題，請無視 XD
08/01 17:05, 2F
推
08/01 17:22, , 3F
樓上的理解其實也沒錯, 稍微轉化一下, 即可適用此題 :)
08/01 17:22, 3F
→
08/01 17:27, , 4F
可以請 yvb 大開示一下嗎 :)
08/01 17:27, 4F
推
08/01 18:48, , 5F
用線段樹可以做到O(n log n)..感覺有別的方法OAO
08/01 18:48, 5F
推
08/01 18:56, , 6F
08/01 18:56, 6F
推
08/01 18:59, , 7F
這是相關文章，搜尋 逆序數對+樹狀數組應該可以搜到很多
08/01 18:59, 7F
→
08/01 18:59, , 8F
東西
08/01 18:59, 8F
推
08/01 19:04, , 9F
推月神 <(_ _)>
08/01 19:04, 9F
推
08/01 19:54, , 10F
如果是單純算inversion 用線段樹會比較快嘛？
08/01 19:54, 10F
推
08/01 22:49, , 11F
如果mergesort排序可以一邊排，一邊數inversions
08/01 22:49, 11F
推
08/02 07:49, , 12F
我也是這樣覺得 使用線段數有什麼好處嘛？
08/02 07:49, 12F
推
08/03 00:18, , 13F
線段樹可以處理動態情況，例如每次修改某個數字
08/03 00:18, 13F
推
08/03 20:37, , 14F
那當問題是靜態的時候 線段樹應該就沒有優勢了吧?
08/03 20:37, 14F
推
08/03 20:52, , 15F
時間複雜度都一樣 有沒有優勢就看實作功力囉
08/03 20:52, 15F
推
08/04 13:38, , 16F
可能沒有. 當然比賽時線段樹可能有模板, 可以直接套.
08/04 13:38, 16F
→
08/04 13:38, , 17F
但他常數也可能比較大啦 只不過是 trade-off
08/04 13:38, 17F
推
08/20 13:29, , 18F
Ni+1,Ni+2,Ni+3...Nn=>有序遞增, i.e; 3,4,5,6,7,8,9..
08/20 13:29, 18F
→
08/20 13:30, , 19F
輸入 8 => 輸出 (8-3) = 5
08/20 13:30, 19F
→
08/20 13:30, , 20F
哈~~~~ 輕鬆一下...
08/20 13:30, 20F
推
10/03 09:50, , 21F
归并树 / 划分树
10/03 09:50, 21F
‣ 更多 cutekid 的文章
文章代碼(AID): #1JsrHNZT (Prob_Solve)
‣ 更多 cutekid 的文章
文章代碼(AID): #1JsrHNZT (Prob_Solve)