作者CoNsTaR ((const *))
看板Prob_Solve
标题[讨论] Leetcode #283 Move zeroes
时间Thu Oct 24 16:38:08 2019
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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1571906291.A.2CC.html
1F：→ CoNsTaR: 刚刚用 C++ 在 Leetcode AC 了10/24 17:06
3F：→ CoNsTaR: 看到 c++ stable_sort 的 discussion 了，抱歉眼残10/24 17:30
4F：推 ckc1ark: 常见的stable sort其实都不算in-place10/24 23:51
5F：推 ckc1ark: 这题的follow-up就是分<0 和>=0 两边都要stable10/24 23:55
非零都相等应该不论 > 或 < 零都是 stable 才对?
要是再加一条零等於零的话 = 应该也会是 stable
6F：推 bibo9901: 因为sort要O(nlgn) 但这题只需要O(n)?10/25 01:25
请问阵列里只有0(零)与1(非零)两种东西的话还会是 nlgn 吗
我用 Rust 的 AC runtime 0ms，space 2.7mb，照理来讲不会有这个效能吧？
※ 编辑: CoNsTaR (174.112.166.163 加拿大), 10/25/2019 08:35:06
7F：推 FRAXIS: C++ 不能用 partition 直接解吗？10/25 10:54
8F：→ FRAXIS: comparison-based sort 就算输入只有 0 和 1 应该都n lg n10/25 10:54
9F：→ FRAXIS: 就看 library 实作有没有特别对这种 case 最佳化10/25 10:55
partition 的确更好！
不解的是 Rust 的效能，一样的演算法，C++ 跑了 16ms/9.4MB，为什麽 Rust 可以 0ms/
2.7MB...
※ 编辑: CoNsTaR (174.112.166.163 加拿大), 10/25/2019 18:43:04
10F：→ CoNsTaR: 我 submitted 的 Rust 10/25 18:53
12F：→ firejox: 我记得c/c++的优化好像有拿掉过 10/26 15:28