求个能 beats 90% 以上的 Move Zeroes 算法

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3046 天前的主题，其中的信息可能已经有所发展或是发生改变。

题目： 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;
	}
};

29 条回复 • 2016-09-22 19:45:27 +08:00

yongzhong

2016-07-21 19:21:53 +08:00

号称 95 的一般都是很早以前提交的,其他人拿他的答案刷一刷,比率就降下来了

soli

2016-07-21 22:28:25 +08:00

@yongzhong 但是我改了一版和他的一样的，还是 27% 哈。所以，我觉得应该有更好的。

breeswish

2016-07-21 22:34:32 +08:00

算法不复杂，所以时间太短，不稳定因素比较多导致测量不准确
不信你多交几遍同样的代码，可能就某次刷到前 10%了

mengzhuo

2016-07-22 00:20:33 +08:00

呃……为啥你有三个循环
明明一个就成了啊

Valyrian

2016-07-22 05:43:01 +08:00

20ms...
这点时间能说明啥。。误差都比这个长

yaoyuan7571

2016-07-22 10:18:03 +08:00

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--;
}
}

soli

2016-07-22 12:09:12 +08:00

@mengzhuo 一个循环的话，会多几次没用的赋值或判断。并且，那个号称 beats 95% 的和这个逻辑一样。

我也试过用一个循环的，也是 20ms 。

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++;
}
}
}
}
}
```

flyingghost

2016-07-22 12:14:43 +08:00

。。。不是说好了支持 markdown 的吗？

soli

2016-07-22 12:16:11 +08:00

@yaoyuan7571 太神奇了！这个能 beats 94.91% ！

多谢多谢。

我去研究一下这个为啥快。

soli

2016-07-22 12:18:36 +08:00

@flyingghost 说来奇怪，很多这种算法题，用 Java 反而测出来的性能更高。

Java > C++ > C 。。。很无语

提交之后去看『 Submission Details 』，那里有个图表可以看到 beats ，还可以在各种语言之间比较。

soli

2016-07-22 12:29:08 +08:00

@breeswish 我擦！真坑啊！果然是误差！

我连续提交了几次相同的代码，每次结果都不一样！终于有一次刷到了 16 ms beats 94.91%！

我又刷了一次上面那位仁兄 @yaoyuan7571 的代码，时间也变了，变成 22ms beats 22.41% 了。

郁闷了好几天，深深地了怀疑自己的智商。。。

soli

2016-07-22 12:33:29 +08:00

@Valyrian 确实是误差！

原以为『多次测量求平均值』是大家公认的常识呢。谁知道 LeetCode 这么坑。。。

或者用台差点的机器，再把测试用例搞的量大一点，也能降低误差吧。

mengzhuo

2016-07-22 13:51:11 +08:00 via iPhone

@soli 不太清楚 C++
但是 in place 对比哪里来赋值？

mengzhuo

2016-07-22 13:56:26 +08:00 via iPhone

而且都是 O(n)怎么可能有这么大差异？

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;
}
}

fcicq

2016-07-22 14:06:37 +08:00

online judge 也就会用 time 计数. perf 等方法他们不会. 误差太正常.

pathletboy

2016-07-22 14:43:02 +08:00

懒汉版
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);
}
};

YORYOR

2016-07-22 18:00:50 +08:00

YORYOR

2016-07-22 18:01:48 +08:00

java 这竞争。。

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++本来就是为了避免各种指针的使用的啊……

DaCong

2016-07-22 20:22:37 +08:00

@flyingghost 评论不支持 markdown ，只有帖子正文支持

yhylord

2016-07-22 20:43:58 +08:00

@SuperFashi 确实 C++11 的话写迭代器用 auto 就行了巨爽，但是更早的要手动写长长的 vector<int>::iterator 还是挺烦的

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

jeffersonpig

2016-07-23 18:10:43 +08:00

leetcode 的性能数据没个准头的

breeswish

2016-07-24 15:41:10 +08:00

@soli 这个其实没法儿准确测量，撞上时间片调度一下就 10ms 加上去了…

以及各种 OJ 目标并不是准确测量耗时，而是衡量你编写算法的对错，因而只测「答案是否正确」、「是否在指定时间内结束（即算法时间复杂度是否满足需求）」、「资源占用是否在指定空间内（空间复杂度是否满足需求）」，是不会多次运行测量准确时间的，这没意义。

soli

2016-07-25 11:23:51 +08:00

@breeswish 前几题都改好几次，直到改到 beats 90%+ 才算完。还蛮有成就感的。

自从知道这个时间是骗人的，就没动力继续刷了。。。

laobubu

2016-09-21 21:20:27 +08:00

https://ooo.0o0.ooo/2016/09/21/57e288f2d12d3.png

虽然是 C++，但是还是用 C 的方式写了一个，突然感觉碉堡了……

soli

2016-09-22 19:45:27 +08:00

@laobubu 66666666666