一亩三分地论坛

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

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

[Leetcode] Lintcode题目 Continuous Subarray Sum II 有几个test过不了

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

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

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

x
http://www.lintcode.com/en/problem/continuous-subarray-sum-ii/#

在可以循环的数组里面找最大的subarray sum,最开始想的是复制一份数组,然后跟之前的subarray sum一样做,但是有test过不了。然后改进算法,two pass记录第一次的位置然后搜索到当前的index的前一个index,但是这样时间复杂度太高了。看这题AC率才9%,有没有人成功通过的?求共享算法或者代码交流
stellari 发表于 2015-7-6 09:27:03 | 显示全部楼层
最大数组的范围只有两种可能:1. [ i ~ j ],2. [ i ~ N-1] + [ 0 ~ j ]. 所以,你只要分别找到两种情况的最大者,取这两个最大者中较大的即可。1和Continuous Subarray Sum I相同,就不多说了。2等价于找一个范围[j+1 ~i-1],使得这个范围内的数组和最小。这又等价于将原数组取负号,然后在这个负数组中找最大和的[j+1 ~ i+1]范围即可。
回复 支持 1 反对 0

使用道具 举报

glaciersilent 发表于 2015-7-6 10:25:15 | 显示全部楼层
和楼上的想法是一样的,代码如下。感觉逻辑和内存使用上都有优化的空间,目前属于逼近TLE的水平。。楼主随便参考一下就好
  1. public ArrayList<Integer> continuousSubarraySumII(int[] A) {
  2.         // Write your code here
  3.         if(A.length==0)
  4.             return new ArrayList<Integer>();
  5.         int max=Integer.MIN_VALUE;
  6.         int min=Integer.MAX_VALUE;
  7.         ArrayList<Integer> maxIndex=new ArrayList<Integer>();
  8.         ArrayList<Integer> minIndex=new ArrayList<Integer>();
  9.         for(int i=0;i<2;i++){
  10.             maxIndex.add(0);
  11.             minIndex.add(0);
  12.         }
  13.         int[] maxArr=new int[A.length];
  14.         int[] minArr=new int[A.length];
  15.         int[] maxStart=new int[A.length];
  16.         int[] minStart=new int[A.length];
  17.         maxArr[0]=A[0];
  18.         minArr[0]=A[0];
  19.         int sum=A[0];
  20.         for(int i=1;i<A.length;i++){
  21.             sum+=A[i];
  22.             if(maxArr[i-1]>0){
  23.                 maxArr[i]=maxArr[i-1]+A[i];
  24.                 maxStart[i]=maxStart[i-1];
  25.             }
  26.             else{
  27.                 maxArr[i]=A[i];
  28.                 maxStart[i]=i;
  29.             }
  30.             if(minArr[i-1]<0){
  31.                 minArr[i]=minArr[i-1]+A[i];
  32.                 minStart[i]=minStart[i-1];
  33.             }
  34.             else{
  35.                 minArr[i]=A[i];
  36.                 minStart[i]=i;
  37.             }
  38.             if(maxArr[i]>max){
  39.                 max=maxArr[i];
  40.                 maxIndex.set(0,maxStart[i]);
  41.                 maxIndex.set(1,i);
  42.             }
  43.             if(minArr[i]<min){
  44.                 min=minArr[i];
  45.                 minIndex.set(0,(i+1)%A.length);
  46.                 minIndex.set(1,minStart[i]-1>=0?minStart[i]-1:A.length-1);
  47.             }
  48.         }
  49.         if(max>sum-min||min==sum)
  50.             return maxIndex;
  51.         else
  52.             return minIndex;
  53.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| stevenlordiam 发表于 2015-7-6 10:31:45 | 显示全部楼层
stellari 发表于 2015-7-6 09:27
最大数组的范围只有两种可能:1. [ i ~ j ],2. [ i ~ N-1] + [ 0 ~ j ]. 所以,你只要分别找到两种情况的 ...

我后来想的改进方法就是这样的  可是时间复杂度太高了  在lintcold上超过1wms了 觉得可以有更好的方法
回复 支持 反对

使用道具 举报

 楼主| stevenlordiam 发表于 2015-7-6 10:32:19 | 显示全部楼层
glaciersilent 发表于 2015-7-6 10:25
和楼上的想法是一样的,代码如下。感觉逻辑和内存使用上都有优化的空间,目前属于逼近TLE的水平。。楼主随 ...

我也是这个想法  还没想到更好的 lintcode上跑时间太久了
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-7-6 10:45:52 | 显示全部楼层
stevenlordiam 发表于 2015-7-6 10:32
我也是这个想法  还没想到更好的 lintcode上跑时间太久了

one pass O(n)算法已经是理论上最优了,当然我觉得可以靠多判断或者摆弄array之类的少用内存少存取来提高速度 我感觉lintcode的时间随便看看就好。。很简单的题和很复杂的题都可以到1w以上 又没有百分比 不像LC的有参考价值。。这题的阈值我觉得可能是2W,目前这个算法最好可以有1w2左右
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-6 11:02:32 | 显示全部楼层
stevenlordiam 发表于 2015-7-6 10:31
我后来想的改进方法就是这样的  可是时间复杂度太高了  在lintcold上超过1wms了 觉得可以有更好的方法

时间复杂度和实际执行时间没有必然联系啊。这个算法的时间复杂度是O(N),不可能比这个时间复杂度再优了。实际执行时间过长可能是因为后台的测试用例太大的缘故。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-6 11:19:31 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-6 11:21 编辑
glaciersilent 发表于 2015-7-6 10:45
one pass O(n)算法已经是理论上最优了,当然我觉得可以靠多判断或者摆弄array之类的少用内存少存取来提高 ...

运行时间长是因为java真的很慢,常系数太大。。复杂度没有问题的,不论是one pass还是two pass
换成C++写一遍的话,时间会短很多的。有些OJ上用C++的vector、cin都超时,必须改成数组、scanf。复杂度的常系数差别有时很惊人。
回复 支持 反对

使用道具 举报

 楼主| stevenlordiam 发表于 2015-7-6 11:20:12 | 显示全部楼层
stellari 发表于 2015-7-6 11:02
时间复杂度和实际执行时间没有必然联系啊。这个算法的时间复杂度是O(N),不可能比这个时间复杂度再优了。 ...

对 我开始想错了 我的做法类似的two pass 应该是2N = N
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2015-7-26 06:11:14 | 显示全部楼层
stevenlordiam 发表于 2015-7-6 10:31
我后来想的改进方法就是这样的  可是时间复杂度太高了  在lintcold上超过1wms了 觉得可以有更好的方法


这个题可以分两步啊, 第一步和Continuous Subarray Sum相同,第二步相当于求 -A 的Continuous Subarray Sum, 然后看看第一步的结果和 数组总和减掉第二步的结果 哪个大,就知道是否是循环数组了。 我用C++的结果是1Kms左右
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 13:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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