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

[soli]

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

[yongzhong]

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

[soli]

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

[breeswish]

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

[mengzhuo]

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

[Valyrian]

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

[yaoyuan7571]

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]

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

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

[flyingghost]

哪里参加 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]

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

[soli]

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

多谢多谢。

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

[soli]

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

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

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

[soli]

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

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

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

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

[soli]

@Valyrian 确实是误差！

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

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

[mengzhuo]

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

[mengzhuo]

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

[lawlietxxl]

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]

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

[pathletboy]

懒汉版
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]

[YORYOR]

java 这竞争。。