首页 > 学院 > 开发设计 > 正文

一道算法题的一种O(n)解法

2019-11-17 03:49:27
字体:
来源:转载
供稿:网友
很早就有去做做的想法,可是一直没动手

今天花了点时间搞搞

结果如下:

核心部分





代码
1  public List<Result> GetResults(int[] arr)
2         {
3             //输入有效性检测
4             if (arr.Length==0)
5                 throw new NotEnoughInputException();
6
7             List<Result> rlist = new List<Result>();
8             
9             //实际运算
10             
11             //初始化起始位置,将第一点当作后续结果的起点
12             Position startP = new Position(Position.EmptyPosition, arr[0]);
13
14             //当前点就当作是最大结果值
15             Result curResult = new Result(Position.EmptyPosition, startP);
16
17             //向结果列表添加内容
18             rlist.Add(curResult);
19
20             //有一个以上的数据
21             if (arr.Length > 1)
22             {
23                 Position curP,nextP;
24                 curP=startP;
25                 Result temp;//保存到目前点为止的结果数据
26                 //从第二个点开始逐个判断
27                 for (int i = 1; i < arr.Length; i++)
28                 {
29                     //构造对象
30                     nextP = new Position(curP,arr[i]);
31                     temp = new Result(startP, nextP);
32
33                     //判断当前的和是否大于现有结果列表中的数据
34                     if (temp.RelativeElevation > rlist[0].RelativeElevation)
35                     {//如果大于则清除结果列表,添加当前结果
36                         rlist.Clear();
37                         rlist.Add(temp);
38                     }
39                     //判断当前的和是否等于现有结果列表中的数据
40                     else if (temp.RelativeElevation == rlist[0].RelativeElevation)
41                     {
42                         rlist.Add(temp);
43                     }
44                     //判断当前是否是一个新的低点
45                     else if(nextP.EndElevation<=startP.StartElevation)
46                     {
47                         startP = nextP;
48                     }
49                     curP = nextP;
50                 }
51             }           
52
53             return rlist;
54         }




代码还有进一步优化的余地

主体思想就是模拟一个不断爬山的人,爬完一遍后要回答那座山和山谷的相对落差最大

完整代码在此

主要多用了些类,呵呵。

局部代码有些不好理解,呵呵。比如里面关于全负数的处理。

欢迎拍砖  


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表