一亩三分地论坛

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

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

[算法题] 4sum, 这样写算是O(N^2)么?

[复制链接] |试试Instant~ |关注本帖
plich 发表于 2015-10-20 00:14:10 | 显示全部楼层 |阅读模式

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

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

x

思路分为三步:                                                                     
1. sorting
2. 建立一个map,可以把任一加和值映射到一系列tuple里 在我的tuple里前两个数是数组中的数, 且第一个小于第二个,而第三个则是第一个数的index
比如 给定数组 A={1 2 3 4 5 6},那么 5 ->  {(1,4,0) (2,3,1)}   3->{(1,2,0)}
3.  用两个index  i,j 搜索答案 如果发现target-nums-nums[j]所映射的tuple里面第三位index 比j大,那么nums,nums[j]以及tuple里面的两个数就会组成一个可行解

另有一些小优化,bypass 掉了很多不需要考虑的情况和不需要记录到map里面的tuple。

我想知道第三步的复杂度可否认为是O(n^2)……这么写是要比O(n^3)快的(20ms 对比 60ms),但总有一种worst case O(n^3)的感觉
  1. struct Mtuple{
  2.     Mtuple(int A,int B,int K){
  3.         a=A;
  4.         b=B;
  5.         k=K;
  6.     }
  7.    
  8.     int a;
  9.     int b;
  10.     int k;//index
  11. };

  12. class Solution {
  13. public:
  14.     vector<vector<int>> fourSum(vector<int>& nums, int target) {
  15.         vector<vector<int>>result;
  16.         int n=nums.size();
  17.         if(n<4)return result;
  18.         
  19.         int i,j,k,temp;
  20.         vector<int> cache;
  21.         
  22.         sort(nums.begin(),nums.end());
  23.         unordered_map<int,vector<Mtuple> > map;//send number to tuples; 4 |-> (1,3,2)
  24.         
  25.         vector<Mtuple> fill;
  26.         
  27.         for(i=n-1;i>=3;i--){
  28.             if(i!=n-1)
  29.                 if(nums[i]==nums[i+1])
  30.                     continue;
  31.                     
  32.             if(nums[i]+nums[i-1]+nums[i-2]+nums[i-3]<target)//opt 1st
  33.                 break;
  34.             if(nums[i]+nums[0]+nums[1]+nums[2]>target)//opt 1st
  35.                 continue;
  36.             
  37.             for(j=i-1;j>=2;j--){
  38.                
  39.                 if(nums[j]==nums[j+1] && j!=i-1)
  40.                     continue;
  41.                     
  42.                 if(nums[i]+nums[j]+nums[j-1]+nums[j-2]<target)//opt 1st
  43.                     break;
  44.                 if(nums[i]+nums[j]+nums[0]+nums[1]>target)//opt 1st
  45.                     continue;
  46.                
  47.                 temp=nums[i]+nums[j];
  48.                
  49.                 if(map.find(temp) == map.end()){
  50.                     fill.clear();
  51.                     fill.push_back(Mtuple(nums[j],nums[i],j));
  52.                     map[temp]=fill;
  53.                 }
  54.                 else{
  55.                     map[temp].push_back(Mtuple(nums[j],nums[i],j));
  56.                 }
  57.             }
  58.         }
  59.         
  60.         for(i=0;i<=n-4;i++){
  61.             if(i)
  62.                 if(nums[i]==nums[i-1])
  63.                     continue;
  64.                     
  65.             if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target)
  66.                 continue;
  67.             if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target)
  68.                 break;
  69.                     
  70.             for(j=i+1;j<=n-3;j++){
  71.                 if(nums[j]==nums[j-1] && j!=i+1)
  72.                     continue;
  73.                
  74.                 if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target)
  75.                     continue;
  76.                 if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target)
  77.                     break;
  78.                
  79.                 temp=nums[i]+nums[j];
  80.                 if(map.find(target-temp) != map.end()){
  81.                     for(k=0;k< map[target-temp].size();k++){
  82.                         if(map[target-temp][k].k>j){
  83.                             cache=vector<int>({nums[i],nums[j],map[target-temp][k].a,map[target-temp][k].b});
  84.                             result.push_back(cache);
  85.                         }
  86.                     }
  87.                 }
  88.             }
  89.         }
  90.         
  91.         return result;
  92.     }
  93. };
复制代码
storm_hair 发表于 2015-10-20 00:35:57 | 显示全部楼层
是的是的是的
回复 支持 反对

使用道具 举报

yinzhihong12 发表于 2015-10-26 16:49:20 | 显示全部楼层
worst case O(n^3). it can not be solved by O(n^2).
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-26 22:22:30 | 显示全部楼层
yinzhihong12 发表于 2015-10-26 16:49
worst case O(n^3). it can not be solved by O(n^2).

多谢……那你觉得worst case是什么形状的例子……或者说具体点什么例子是n^3的呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 18:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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