设为首页收藏本站订阅更新

无忧脚本

 找回密码
 加入无忧

QQ登录

只需一步,快速开始

搜索
查看: 2852|回复: 0

一道算法题的求解

[复制链接]
发表于 2012-4-1 18:19:16 | 显示全部楼层 |阅读模式
本帖最后由 LichScript 于 2012-4-2 13:35 编辑

在微博上看到的一道算法题: http://weibo.com/2039445353/ycr2npl5O
给定一个 array,求出里面最长的连续的一段,它由连续的数组成,顺序任意。例如 (5 1 3 2) 就返回 (1 3 2),(5 3 1 4 2) 就返回 (5 3 1 4 2)


解题思路: 对于数组范围[l,r],从该范围中找出最大最小值a,b,计算a,b的差值,如果差值刚好等于l,r的差值,则该范围是整体连续的,记下该结果;  如果不等于,则将范围拆分成两部分,设a,b下标分别为Ia,Ib;拆分为 [l,Ib-1],[Ia+1,Ib],递归找出最优值.


具体代码:
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
  2. <html xmlns="http://www.w3.org/1999/xhtml">
  3. <head>
  4. <meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
  5. <title>无标题文档</title>
  6. <script type="text/javascript" src="JQuery.js"></script>
  7. <script type="text/javascript">
  8.         var arr = [4,2,1,7,8,9,5,15,12,11,9,10];
  9.         //返回最大最小值在数组中的下标, 每躺比较的次数为 1.5(r-l)
  10.         function findMinMax(arr, l, r){
  11.                 if( l == r )    return [l,l];
  12.                 var a = l, b = l+1;
  13.                 if( arr[a] > arr[b] ){
  14.                         a = b;
  15.                         b = l;
  16.                 }
  17.                 var n1, n2;
  18.                 for(var i=l+2;i<=r;){
  19.                         if( i+1 <= r ){
  20.                                 if( arr[i] > arr[i+1] ){
  21.                                         n1 = i+1;
  22.                                         n2 = i;
  23.                                 }else{
  24.                                         n1 = i;
  25.                                         n2 = i+1;
  26.                                 }
  27.                                 if( arr[a] > arr[n1] ) a = n1;
  28.                                 if( arr[b] < arr[n2] ) b = n2;
  29.                                 i += 2;
  30.                         }
  31.                         else{
  32.                                 if( arr[a] > arr[i] ) a = i;
  33.                                 if( arr[b] < arr[i] ) b = i;
  34.                                 return [a,b];
  35.                         }
  36.                 }
  37.                 return [a,b];
  38.         }
  39.         
  40.         var best = [];
  41.         function  findMaxSeq(arr, L, R){
  42.                 if( L >= R )
  43.                         return ;
  44.                 var mm = findMinMax(arr,L,R);
  45.                
  46.                 if( Math.abs(arr[mm[1]] - arr[mm[0]]) == R-L ){
  47.                         if( !best.length ||  ( (best[1] - best[0]) < R-L) ){
  48.                                 best = [L,R];
  49.                         }
  50.                 }else{
  51.                         if( mm[0] < mm[1] ){
  52.                                 findMaxSeq(arr,L,mm[1]-1);
  53.                                 findMaxSeq(arr,mm[0]+1,R);
  54.                         }
  55.                         else{
  56.                                 findMaxSeq(arr,L,mm[0]-1);
  57.                                 findMaxSeq(arr,mm[1]+1,R);
  58.                         }
  59.                 }
  60.         }
  61.         
  62.         findMaxSeq(arr, 0, arr.length-1);
  63.         var rst = [];
  64.         for(var i=best[0];i<=best[1];i++){
  65.                 rst.push(arr[i]);
  66.         }
  67.         alert('result: '+ rst.join(','));
  68. </script>
  69. </head>
  70. <body>
  71. </body>
  72. </html>
复制代码
算法复杂度为 O(nlogn + n^2) , 求吐槽,有没更好的解法?

您需要登录后才可以回帖 登录 | 加入无忧

本版积分规则

小黑屋|手机版|Archiver|无忧脚本 ( 苏ICP备05080427号 )|值班电话:027-62300445   鄂公网安备 42011102000433号

GMT+8, 2017-11-23 19:06 , Processed in 0.092940 second(s), 8 queries , Gzip On, Memcache On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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