一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 831|回复: 17
收起左侧

[Leetcode] 3sum 时间复杂度问题

[复制链接] |试试Instant~ |关注本帖
caffery24 发表于 2015-7-8 12:32:36 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
3sum这个题目中,如果用hashset来判断,不知道为什么就会出现tle,我感觉两种方法的时间没有本质差别啊,请大家解答下,重点是在找到了3个数以后那一部分。
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result=new ArrayList<List<Integer>>();
//   Set<List<Integer>> set=new HashSet<List<Integer>>()
    int i=0,j=i+1,k=nums.length-1;
    Arrays.sort(nums);
    for(i=0;i<nums.length-2&&nums[i]<=0;i++)
    { j=i+1;k=nums.length-1;
       if(i==0||(i>0&&nums[i]!=nums[i-1]))
       {while(j<k)
        {
            if(nums[i]+nums[j]+nums[k]==0)
            {List<Integer> res=new ArrayList<Integer>();
                res.add(nums[i]);
                res.add(nums[j]);
                res.add(nums[k]);
                result.add(res);
                while(j<k&&nums[j]==nums[j+1])j++;
                while(j<k&&nums[k]==nums[k-1])k--;
                j++;k--;
            }
            else if(nums[i]+nums[j]+nums[k]>0)
            {
            k--;
            }
            else {
            j++;
            }
        }
       }
    }
    return result;
    }
}

这个事ac通过了的,判处重复的方法是通过跳过已经判断过的j,k;
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result=new ArrayList<List<Integer>>();
    Set<List<Integer>> set=new HashSet<List<Integer>>();
    int i=0,j=i+1,k=nums.length-1;
    Arrays.sort(nums);
    for(i=0;i<nums.length-2;i++)
    { j=i+1;k=nums.length-1;
        while(j<=nums.length-2&&j<k)
        {List<Integer> res=new ArrayList<Integer>();
            if(nums[i]+nums[j]+nums[k]==0)
            {
                res.add(nums[i]);
                res.add(nums[j]);
                res.add(nums[k]);
                if(set.add(res)
                {result.add(res);
                }
                j++;
                k--;
            }
            else if(nums[i]+nums[j]+nums[k]>0)
            k--;
            else
            j++;
        }
    }
    return result;
    }
}

这个是使用了hashset来判断重复,不知道对不对,我记得hashset.add是O(1)的时间复杂度啊,为什么会超过了time呢???

不知道正不正常,感觉现在做难度3的题很多想了好久都没一个完整的思路,都是些碎片,最后得看了别人的思路才行,内心十分纠结,但是不看又写不出来。。。好痛苦,希望能逐渐的学会别人的精华,做到自己写出来
zhuli19901106 发表于 2015-7-8 12:56:31 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-8 12:58 编辑

楼主加个代码缩进吧,都四层括号了,可读性实在太低。
你可以通过改写代码减少括号层数。
另外,用括起来,这样能保留格式
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-7-8 13:01:36 | 显示全部楼层
zhuli19901106 发表于 2015-7-8 12:56
楼主加个代码缩进吧,都四层括号了,可读性实在太低。
你可以通过改写代码减少括号层数。
另外,用括起来 ...

嗯嗯,谢谢啊。。。这个是刚才实在想不通改烦了,也没注意格式,
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-8 13:13:49 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-8 13:18 编辑
caffery24 发表于 2015-7-8 13:01
嗯嗯,谢谢啊。。。这个是刚才实在想不通改烦了,也没注意格式,

而且第二份代码连括号都没匹配。。改了改以后,第二份代码也可以ac
两者的效率几乎没有差别,一个2071ms,一个2085ms
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-7-8 13:29:38 | 显示全部楼层
zhuli19901106 发表于 2015-7-8 13:13
而且第二份代码连括号都没匹配。。改了改以后,第二份代码也可以ac
两者的效率几乎没有差别,一个2071ms ...

第二个确实我是tle了啊,不知道是因为什么,刚才看了discuss有人也是用hashset超时了
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-8 13:47:31 | 显示全部楼层
caffery24 发表于 2015-7-8 13:29
第二个确实我是tle了啊,不知道是因为什么,刚才看了discuss有人也是用hashset超时了

两份代码我都读了,感觉第一种更好。不过两份都有没找到bug,在lintcode上试了试也都ac了。
你是在leetcode上超时吗?预期复杂度应该是O(n^2)
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-8 14:33:26 | 显示全部楼层
我记得我很久以前用hash好像也跪了,也是觉得奇怪,不知道是不是hash的overhead导致超时了。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-8 14:44:47 | 显示全部楼层
试了试,leetcode还真超时了,莫非leetcode上的时间给的短点?那超时也就不奇怪了,常系数优化吧。反正算法的正确性应该是没问题。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-8 14:47:00 | 显示全部楼层
记得当年做一道POJ的题目,2000ms的限制,我搞出过一个1999ms的ac,嘿嘿~~
实际上用些常数优化的方法,就能把时间降下去的。
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-8 15:07:07 | 显示全部楼层
呃,我发现我的旧code为啥超时了,因为我的算法错了囧。。。
我用的set去重元素,但元素可以重复用,改成map就过了。楼主这个set和我用法不一样,结果应该正确,但是这个做法不能剪枝,所以超时吧。
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-7-8 21:43:12 | 显示全部楼层
zhuli19901106 发表于 2015-7-8 13:47
两份代码我都读了,感觉第一种更好。不过两份都有没找到bug,在lintcode上试了试也都ac了。
你是在leetc ...

第二种用hash的情况在leetcode上就超时了,不知道为什么
回复 支持 反对

使用道具 举报

 楼主| caffery24 发表于 2015-7-8 21:44:00 | 显示全部楼层
handsomecool 发表于 2015-7-8 15:07
呃,我发现我的旧code为啥超时了,因为我的算法错了囧。。。
我用的set去重元素,但元素可以重复用,改成m ...

意思是有很多重复的情况,都全部判断了一遍吗?所以超时了
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-8 23:16:47 | 显示全部楼层
caffery24 发表于 2015-7-8 21:44
意思是有很多重复的情况,都全部判断了一遍吗?所以超时了

应该是这样。比如[1 1 1 1 1 1 1 1 2 -3] 这个例子。本来找到第一个[1 2 -3]时,后面的1都可以直接跳过了。而第二段代码中还是坚持不懈地查询了后面的所有[1 2 -3]组合。两个代码最差时间复杂度一样,但是当有大量重复的时候,第一段代码事实上就接近O(N)了,而后者在任何情况下都是雷打不动的O(N^2)。而且第二段代码还创建了大量的不必要的ArrayList(即res)。我不知道垃圾回收的时间算不算在OJ的计时里,但是不管怎么说,这种本来不必要的创建-删除循环肯定会拖慢程序的效率。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-8 23:17:38 | 显示全部楼层
caffery24 发表于 2015-7-8 21:43
第二种用hash的情况在leetcode上就超时了,不知道为什么

我是用C++写的,同样的方法。
于是java就是这么慢~常系数太大
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-8 23:25:00 | 显示全部楼层
求破 n2的解法, 造福全世界
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-9 10:56:44 | 显示全部楼层
readman 发表于 2015-7-8 23:25
求破 n2的解法, 造福全世界

你确定有更优复杂度的解?
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-9 11:58:56 | 显示全部楼层
zhuli19901106 发表于 2015-7-9 10:56
你确定有更优复杂度的解?

没, 等某人造福世界呢
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-9 12:15:59 | 显示全部楼层
readman 发表于 2015-7-9 11:58
没, 等某人造福世界呢

不如叫sharkwolf来试试,本版块数他最牛~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 02:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表