一亩三分地论坛

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

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

[算法题] 大家来一起讨论一下4sum的o(n^2)的解法吧

[复制链接] |试试Instant~ |关注本帖
f1371342385 发表于 2015-9-8 04:26:03 | 显示全部楼层 |阅读模式

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

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

x
对于4sum的O(n^2)的解法,我的解法是首先把数组中得值相互相加,然后存入HashMap<Integer, List<Integer>>中,list中存的是下标,然后按照3sum的解法来,因为hashmap的值应该不会聚集,所以认为在hashmap中查是常数。所以,整体的时间复杂度可以认为O(n^2),求问各位大神,俺的解法对不对呀
lichuanr 发表于 2015-9-8 05:11:52 | 显示全部楼层
本帖最后由 lichuanr 于 2015-9-8 05:13 编辑

我觉得是对的。如果average hash_value's length is K. the run time will be O(k*n^2)
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-8 06:04:56 | 显示全部楼层
放心,不会考
回复 支持 反对

使用道具 举报

ghost33 发表于 2015-9-8 07:43:41 | 显示全部楼层
4sum 最低是 O(n^2logn) 吧
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 2015-9-8 07:46:00 | 显示全部楼层
ghost33 发表于 2015-9-8 07:43
4sum 最低是 O(n^2logn) 吧

那个logn是那儿来的?在处理hashmap的时候?求代码
回复 支持 反对

使用道具 举报

ghost33 发表于 2015-9-8 07:47:04 | 显示全部楼层
logn 是排序的时候产生的
回复 支持 反对

使用道具 举报

ghost33 发表于 2015-9-8 07:48:45 | 显示全部楼层
求和后得到 n*(n-1)/2 长度的数组, 再排序后用two 的sum的方法, 问题是去重很复杂。 面试最好不要用这种方法。
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 2015-9-8 07:55:08 | 显示全部楼层
public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        HashMap<Integer, List<List<Integer>>> hashmap = new HashMap<Integer, List<List<Integer>>>();
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 1; i++){
            for(int j = i + 1; j < nums.length; j++){
                int val = nums[i] + nums[j];
                if(hashmap.containsKey(val)){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(i);
                    list.add(j);
                    hashmap.get(val).add(list);
                }else{
                    List<List<Integer>> lists = new ArrayList<List<Integer>>();
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(i);
                    list.add(j);
                    lists.add(list);
                    hashmap.put(val, lists);
                }
            }
        }
        
        for(int i = 0; i < nums.length - 1; i++){
            for(int j = i + 1; j < nums.length; j++){
                int val = target - nums[i] - nums[j];
                if(hashmap.containsKey(val)){
                    List<List<Integer>> lists = hashmap.get(val);
                    for(int k = 0; k < lists.size(); k++){
                        List<Integer> list = new ArrayList<Integer>();
                        if(lists.get(k).contains(i) || lists.get(k).contains(j))
                            continue;
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[lists.get(k).get(0)]);
                        list.add(nums[lists.get(k).get(1)]);
                        Collections.sort(list);
                        if(!set.contains(list)){
                            ans.add(list);
                            set.add(list);
                        }
                    }
                }
            }
        }
        return ans;
    }
我这个去重比较简单,不知道是不是完成了时间复杂度最优呀
回复 支持 反对

使用道具 举报

ghost33 发表于 2015-9-8 08:44:57 | 显示全部楼层
你时间复杂度很能很大。 主要是 hashmap 里的list 可能很长
回复 支持 反对

使用道具 举报

ghost33 发表于 2015-9-8 08:48:25 | 显示全部楼层
比如  target 为 0, nums = [-1,1,-1,1,-1,1,.......],  
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-9-8 08:54:20 | 显示全部楼层
有趣的做法~
好像有一个问题,如果input里有重复的数字,你去重的那里就会把valid的答案也排除掉了。比如target = 4, input = {1,1,1,1}
我又想到,n个里面选4个, 用组合公式可以算出来 C(n, 4) = 1/24*n(n-1)*(n-2)*(n-3) 这样貌似输出最多可以到n^4那么多?
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 2015-9-8 09:00:55 | 显示全部楼层
handsomecool 发表于 2015-9-8 08:54
有趣的做法~
好像有一个问题,如果input里有重复的数字,你去重的那里就会把valid的答案也排除掉了。比如t ...

有道理 不能这么简单的去重复啦
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 2015-9-8 09:01:19 | 显示全部楼层
ghost33 发表于 2015-9-8 08:48
比如  target 为 0, nums = [-1,1,-1,1,-1,1,.......],

求您o(n^2 logn)的代码哈
回复 支持 反对

使用道具 举报

ghost33 发表于 2015-9-8 09:05:54 | 显示全部楼层
f1371342385 发表于 2015-9-8 09:01
求您o(n^2 logn)的代码哈

你在网上随便搜一下就可以搜到O(n^2logn)的。
回复 支持 反对

使用道具 举报

 楼主| f1371342385 发表于 2015-9-8 09:58:15 | 显示全部楼层
ghost33 发表于 2015-9-8 09:05
你在网上随便搜一下就可以搜到O(n^2logn)的。

感谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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