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

简介:

 万仓一黍 同学发了一些文章 

一道算法题,看看大家的思路 

一道算法题,看看大家的思路(续) 

很早就有去做做的想法,可是一直没动手

今天花了点时间搞搞

结果如下:

核心部分

 

 

复制代码
代码
 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         } 
复制代码

 

 

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

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

 完整代码在此

 主要多用了些类,呵呵。

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

欢迎拍砖  

 

作者: 徐少侠
出处: http://www.cnblogs.com/Chinese-xu/

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。
如有问题,可以通过 Chinese_Xu@126.com 联系我,非常感谢。

分享家:Addthis中文版
分类: .Net, C#
标签: C#, 算法

本文转自徐少侠博客园博客,原文链接:http://www.cnblogs.com/Chinese-xu/archive/2010/02/21/1670672.html,如需转载请自行联系原作者
相关文章
python 算法 两数之和 的多种解法
python 算法 两数之和 的多种解法
|
7月前
|
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
87 6
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
73 1
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
97 1
|
7月前
|
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
79 0
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
69 0
python 算法 两数相加多种解法
python 算法 两数相加多种解法
Leetcode算法系列| 1. 两数之和(四种解法)
Leetcode算法系列| 1. 两数之和(四种解法)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等