[討論] Leetcode #283 Move zeroes

看板Prob_Solve (計算數學 Problem Solving)作者 ((const *))時間5年前 (2019/10/24 16:38), 5年前編輯推噓4(408)
留言12則, 5人參與, 5年前最新討論串1/1
https://leetcode.com/problems/move-zeroes/description/ 最直覺的方法是弄一個像這樣的 custom comparater: /// 0 最大,其他通通相等 fn cmp(lhs: N, rhs: N) -> Ord where N: Num { if rhs == 0 { Ord::LT } else if lhs == 0 { Ord::GT } else { Ord::EQ } } 然後用任何 stable sort 排一下就好了 可是小弟菜逼八,在 solutions 和 discussion 裡面都沒看到相關討論 請問這個做法是有什麼毛病嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 174.112.166.163 (加拿大) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1571906291.A.2CC.html

10/24 17:06, 5年前 , 1F
剛剛用 C++ 在 Leetcode AC 了
10/24 17:06, 1F

10/24 17:06, 5年前 , 2F

10/24 17:30, 5年前 , 3F
看到 c++ stable_sort 的 discussion 了,抱歉眼殘
10/24 17:30, 3F

10/24 23:51, 5年前 , 4F
常見的stable sort其實都不算in-place
10/24 23:51, 4F

10/24 23:55, 5年前 , 5F
這題的follow-up就是分<0 和>=0 兩邊都要stable
10/24 23:55, 5F
非零都相等應該不論 > 或 < 零都是 stable 才對? 要是再加一條零等於零的話 = 應該也會是 stable

10/25 01:25, 5年前 , 6F
因為sort要O(nlgn) 但這題只需要O(n)?
10/25 01:25, 6F
請問陣列裡只有0(零)與1(非零)兩種東西的話還會是 nlgn 嗎 我用 Rust 的 AC runtime 0ms,space 2.7mb,照理來講不會有這個效能吧? ※ 編輯: CoNsTaR (174.112.166.163 加拿大), 10/25/2019 08:35:06

10/25 10:54, 5年前 , 7F
C++ 不能用 partition 直接解嗎?
10/25 10:54, 7F

10/25 10:54, 5年前 , 8F
comparison-based sort 就算輸入只有 0 和 1 應該都n lg n
10/25 10:54, 8F

10/25 10:55, 5年前 , 9F
就看 library 實作有沒有特別對這種 case 最佳化
10/25 10:55, 9F
partition 的確更好! 不解的是 Rust 的效能,一樣的演算法,C++ 跑了 16ms/9.4MB,為什麼 Rust 可以 0ms/ 2.7MB... ※ 編輯: CoNsTaR (174.112.166.163 加拿大), 10/25/2019 18:43:04

10/25 18:53, 5年前 , 10F
我 submitted 的 Rust
10/25 18:53, 10F

10/25 18:53, 5年前 , 11F

10/26 15:28, 5年前 , 12F
我記得c/c++的優化好像有拿掉過
10/26 15:28, 12F
文章代碼(AID): #1TiMBpBC (Prob_Solve)
文章代碼(AID): #1TiMBpBC (Prob_Solve)