这是一个创建于 3383 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目： https://leetcode.com/problems/move-zeroes/
开始自己实现了一个，但需要 20ms ，只能 beats 27.02%。
然后去论坛中看了好几个实现，有些号称能 beats 95% ， 但我照着实现、提交后仍然只能 20ms ， beats 27.02%。
论坛中的实现、我的实现都和编辑推荐的算法一样。
语言选的是 C++ 。
附我的实现：
class Solution { public: void moveZeroes(vector<int>& nums) { int i = 0; int l = nums.size(); while (nums[i] != 0 && i < l) ++i; for (int j = i + 1; j < l; ++j) { if (nums[j] != 0) { nums[i++] = nums[j]; } } while(i < l) nums[i++] = 0; } };  | 1 yongzhong 2016-07-21 19:21:53 +08:00 号称 95 的一般都是很早以前提交的,其他人拿他的答案刷一刷,比率就降下来了 |
 | 3 breeswish 2016-07-21 22:34:32 +08:00  1 算法不复杂，所以时间太短，不稳定因素比较多导致测量不准确 不信你多交几遍同样的代码，可能就某次刷到前 10%了 |
 | 4 mengzhuo 2016-07-22 00:20:33 +08:00 呃……为啥你有三个循环 明明一个就成了啊 |
 | 5 Valyrian 2016-07-22 05:43:01 +08:00 1 20ms... 这点时间能说明啥。。误差都比这个长 |
 | 6 a href="/member/yaoyuan7571" class="dark">yaoyuan7571 2016-07-22 10:18:03 +08:00 1 void moveZeroes(vector<int>& nums) { int zero_count=0; for (int i=0; i<nums.size(); i++) { if (nums[i] == 0) { zero_count++; } else { int j=i-zero_count; nums[j] = nums[i]; } } int last = nums.size()-1; for (int i=0;i<zero_count;i++) { nums[last]=0; last--; } } |
 | 7 soli OP |
 | 8 flyingghost 2016-07-22 12:12:08 +08:00 哪里参加 beat ？ 我执行时间是 0ms 。 ```java public class Solution { public void moveZeroes(int[] nums) { int empty=0; int start=0; for(int i=0;i<nums.length;i++){ if(nums[i]==0){ empty++; } else{ if(empty==0){ start=i+1; } else{ nums[start]=nums[i]; nums[i]=0; start++; } } } } } ``` |
| 9 flyingghost 2016-07-22 12:14:43 +08:00 。。。不是说好了支持 markdown 的吗？ |
| 10 soli OP |
| 11 soli OP @flyingghost 说来奇怪，很多这种算法题，用 Java 反而测出来的性能更高。 Java > C++ > C 。。。很无语 提交之后去看『 Submission Details 』，那里有个图表可以看到 beats ，还可以在各种语言之间比较。 |
| 12 soli OP @breeswish 我擦！真坑啊！果然是误差！ 我连续提交了几次相同的代码，每结果都不一样！终于有一次刷到了 16 ms beats 94.91%！ 我又刷了一次上面那位仁兄 @yaoyuan7571 的代码，时间也变了，变成 22ms beats 22.41% 了。 郁闷了好几天，深深地了怀疑自己的智商。。。 |
| 13 soli OP |
| 15 mengzhuo 2016-07-22 13:56:26 +08:00 via iPhone 而且都是 O(n)怎么可能有这么大差异？ |
 | 16 lawlietxxl 2016-07-22 14:04:12 +08:00 12 行 solution public class Solution { public void moveZeroes(int[] nums) { if(nums.length < 2) return; int idx = 0; for(int n:nums) if(n != 0) nums[idx++] = n; while(idx < nums.length) nums[idx++] = 0; } } |
 | 17 fcicq 2016-07-22 14:06:37 +08:00 online judge 也就会用 time 计数. perf 等方法他们不会. 误差太正常. |
 | 18 pathletboy 2016-07-22 14:43:02 +08:00 1 懒汉版 class Solution { public: static int compvar(const void *one, const void *two) { return *(int*)One==0; } void moveZeroes(vector<int>& nums) { qsort(&nums[0], nums.size(), sizeof(int), compvar); } }; |
 | 19 YORYOR 2016-07-22 18:00:50 +08:00  |
| 20 YORYOR 2016-07-22 18:01:48 +08:00 java 这竞争。。 |
 | 21 SuperFashi 2016-07-22 18:52:34 +08:00 via Android 这误差就是评测机的玄学，像我们这种打 oi 的就得祈祷评测机不出差错，上次写了个博弈论的记忆化搜索，基本上都在 960-990ms 之间，我运气差，交了好几遍都是 1.006s ，一怒之下刷了 5 次，终于不 tle 了。 而且 leetcode 上 java 比 c++快，不高兴。 但是我想吐槽一下两位： @yaoyuan7571 为啥不用迭代器呢…… @pathletboy ……为啥要用 c 的 qsort 和排序函数写法， c++本来就是为了避免各种指针的使用的啊…… |
 | 22 DaCong 2016-07-22 20:22:37 +08:00 @flyingghost 评论不支持 markdown ，只有帖子正文支持 |
 | 23 yhylord 2016-07-22 20:43:58 +08:00 @SuperFashi 确实 C++11 的话写迭代器用 auto 就行了巨爽，但是更早的要手动写长长的 vector<int>::iterator 还是挺烦的 |
 | 24 skydiver 2016-07-22 22:55:11 +08:00 class Solution { public: void moveZeroes(std::vector<int> &nums) { std::stable_partition(nums.begin(), nums.end(), [](int a) { return a != 0;}); } }; 最简单的写法……可惜还是 20ms |
 | 25 jeffersonpig 2016-07-23 18:10:43 +08:00 leetcode 的性能数据没个准头的 |
| 26 breeswish 2016-07-24 15:41:10 +08:00 @soli 这个其实没法儿准确测量，撞上时间片调度一下就 10ms 加上去了… 以及各种 OJ 目标并不是准确测量耗时，而是衡量你编写算法的对错，因而只测「答案是否正确」、「是否在指定时间内结束（即算法时间复杂度是否满足需求）」、「资源占用是否在指定空间内（空间复杂度是否满足需求）」，是不会多次运行测量准确时间的，这没意义。 |
| 27 soli OP |
 | 28 laobubu 2016-09-21 21:20:27 +08:00 https://ooo.0o0.ooo/2016/09/21/57e288f2d12d3.png 虽然是 C++，但是还是用 C 的方式写了一个，突然感觉碉堡了…… |
Select Language