[討論] Leetcode #283 Move zeroes

[CoNsTaR ((const *))]

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
→ CoNsTaR: 剛剛用 C++ 在 Leetcode AC 了
→ CoNsTaR: https://pastebin.com/UfkFiWnr
→ CoNsTaR: 看到 c++ stable_sort 的 discussion 了，抱歉眼殘
推 ckc1ark: 常見的stable sort其實都不算in-place
推 ckc1ark: 這題的follow-up就是分<0 和>=0 兩邊都要stable
非零都相等應該不論 > 或 < 零都是 stable 才對?
要是再加一條零等於零的話 = 應該也會是 stable

推 bibo9901: 因為sort要O(nlgn) 但這題只需要O(n)?
請問陣列裡只有0(零)與1(非零)兩種東西的話還會是 nlgn 嗎
我用 Rust 的 AC runtime 0ms，space 2.7mb，照理來講不會有這個效能吧？
※ 編輯: CoNsTaR (174.112.166.163 加拿大), 10/25/2019 08:35:06
推 FRAXIS: C++ 不能用 partition 直接解嗎？
→ FRAXIS: comparison-based sort 就算輸入只有 0 和 1 應該都n lg n
→ FRAXIS: 就看 library 實作有沒有特別對這種 case 最佳化
partition 的確更好！
不解的是 Rust 的效能，一樣的演算法，C++ 跑了 16ms/9.4MB，為什麼 Rust 可以 0ms/
2.7MB...
※ 編輯: CoNsTaR (174.112.166.163 加拿大), 10/25/2019 18:43:04
→ CoNsTaR: 我 submitted 的 Rust
→ CoNsTaR: https://ideone.com/0NGwpX
→ firejox: 我記得c/c++的優化好像有拿掉過