V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
soli
V2EX  ›  程序员

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

  •  
  •   soli ·
    solicomo · 2016-07-21 19:15:01 +08:00 · 3693 次点击
    这是一个创建于 2807 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目: 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
        1
    yongzhong  
       2016-07-21 19:21:53 +08:00
    号称 95 的一般都是很早以前提交的,其他人拿他的答案刷一刷,比率就降下来了
    soli
        2
    soli  
    OP
       2016-07-21 22:28:25 +08:00
    @yongzhong 但是我改了一版和他的一样的,还是 27% 哈。所以,我觉得应该有更好的。
    breeswish
        3
    breeswish  
       2016-07-21 22:34:32 +08:00   ❤️ 1
    算法不复杂,所以时间太短,不稳定因素比较多导致测量不准确
    不信你多交几遍同样的代码,可能就某次刷到前 10%了
    mengzhuo
        4
    mengzhuo  
       2016-07-22 00:20:33 +08:00
    呃……为啥你有三个循环
    明明一个就成了啊
    Valyrian
        5
    Valyrian  
       2016-07-22 05:43:01 +08:00   ❤️ 1
    20ms...
    这点时间能说明啥。。误差都比这个长
    yaoyuan7571
        6
    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--;
    }
    }
    soli
        7
    soli  
    OP
       2016-07-22 12:09:12 +08:00
    @mengzhuo 一个循环的话,会多几次没用的赋值或判断。并且,那个号称 beats 95% 的和这个逻辑一样。

    我也试过用一个循环的,也是 20ms 。
    flyingghost
        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++;
    }
    }
    }
    }
    }
    ```
    flyingghost
        9
    flyingghost  
       2016-07-22 12:14:43 +08:00
    。。。不是说好了支持 markdown 的吗?
    soli
        10
    soli  
    OP
       2016-07-22 12:16:11 +08:00
    @yaoyuan7571 太神奇了!这个能 beats 94.91% !

    多谢多谢。

    我去研究一下这个为啥快。
    soli
        11
    soli  
    OP
       2016-07-22 12:18:36 +08:00
    @flyingghost 说来奇怪,很多这种算法题,用 Java 反而测出来的性能更高。

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

    提交之后去看『 Submission Details 』,那里有个图表可以看到 beats ,还可以在各种语言之间比较。
    soli
        12
    soli  
    OP
       2016-07-22 12:29:08 +08:00
    @breeswish 我擦!真坑啊!果然是误差!

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

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

    郁闷了好几天,深深地了怀疑自己的智商。。。
    soli
        13
    soli  
    OP
       2016-07-22 12:33:29 +08:00
    @Valyrian 确实是误差!

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

    或者用台差点的机器,再把测试用例搞的量大一点,也能降低误差吧。
    mengzhuo
        14
    mengzhuo  
       2016-07-22 13:51:11 +08:00 via iPhone
    @soli 不太清楚 C++
    但是 in place 对比哪里来赋值?
    mengzhuo
        15
    mengzhuo  
       2016-07-22 13:56:26 +08:00 via iPhone
    而且都是 O(n)怎么可能有这么大差异?
    lawlietxxl
        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;
    }
    }
    fcicq
        17
    fcicq  
       2016-07-22 14:06:37 +08:00
    online judge 也就会用 time 计数. perf 等方法他们不会. 误差太正常.
    pathletboy
        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);
    }
    };
    YORYOR
        19
    YORYOR  
       2016-07-22 18:00:50 +08:00
    YORYOR
        20
    YORYOR  
       2016-07-22 18:01:48 +08:00
    java 这竞争。。
    SuperFashi
        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++本来就是为了避免各种指针的使用的啊……
    DaCong
        22
    DaCong  
       2016-07-22 20:22:37 +08:00
    @flyingghost 评论不支持 markdown ,只有帖子正文支持
    yhylord
        23
    yhylord  
       2016-07-22 20:43:58 +08:00
    @SuperFashi 确实 C++11 的话写迭代器用 auto 就行了巨爽,但是更早的要手动写长长的 vector<int>::iterator 还是挺烦的
    skydiver
        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
    jeffersonpig
        25
    jeffersonpig  
       2016-07-23 18:10:43 +08:00
    leetcode 的性能数据没个准头的
    breeswish
        26
    breeswish  
       2016-07-24 15:41:10 +08:00
    @soli 这个其实没法儿准确测量,撞上时间片调度一下就 10ms 加上去了…

    以及各种 OJ 目标并不是准确测量耗时,而是衡量你编写算法的对错,因而只测「答案是否正确」、「是否在指定时间内结束(即算法时间复杂度是否满足需求)」、「资源占用是否在指定空间内(空间复杂度是否满足需求)」,是不会多次运行测量准确时间的,这没意义。
    soli
        27
    soli  
    OP
       2016-07-25 11:23:51 +08:00
    @breeswish 前几题都改好几次,直到改到 beats 90%+ 才算完。还蛮有成就感的。

    自从知道这个时间是骗人的,就没动力继续刷了。。。
    laobubu
        28
    laobubu  
       2016-09-21 21:20:27 +08:00
    https://ooo.0o0.ooo/2016/09/21/57e288f2d12d3.png

    虽然是 C++,但是还是用 C 的方式写了一个,突然感觉碉堡了……
    soli
        29
    soli  
    OP
       2016-09-22 19:45:27 +08:00
    @laobubu 66666666666
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1909 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 16:25 · PVG 00:25 · LAX 09:25 · JFK 12:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.