C#LeetCode刷题之#414-第三大的数(Third Maximum Number)
问题
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3710 访问。
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
输入: [3, 2, 1]
输出: 1
解释: 第三大的数是 1.
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .
输入: [2, 2, 3, 1]
输出: 1
解释: 注意,要求返回第三大的数,是指第三大且唯一出现的数。
存在两个值为2的数,它们都排第二。
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.
示例
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3710 访问。
public class Program {
public static void Main(string[] args) {
int[] nums = null;
nums = new int[] { 3, 2, 1 };
var res = ThirdMax(nums);
Console.WriteLine(res);
nums = new int[] { 3, 2, 1 };
res = ThirdMax2(nums);
Console.WriteLine(res);
Console.ReadKey();
}
private static int ThirdMax(int[] nums) {
Array.Sort(nums);
int count = 0;
for(int i = nums.Length - 1; i >= 1; i--) {
if(nums[i] != nums[i - 1]) count++;
if(count == 2) {
return nums[i - 1];
}
}
return nums[nums.Length - 1];
}
private static int ThirdMax2(int[] nums) {
var sorted = new SortedSet<int>();
for(int i = 0; i < nums.Length; i++) {
sorted.Add(nums[i]);
if(sorted.Count > 3) {
sorted.Remove(sorted.ElementAt(0));
}
}
return sorted.Count == 3 ? sorted.ElementAt(0) : sorted.ElementAt(sorted.Count - 1);
}
}
以上给出2种算法实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3710 访问。
1
1
分析:
ThirdMax的时间复杂度取决于 Array.Sort() 方法所使用的排序算法:
- 若使用基于比较的先进排序算法,其时间复杂度为: ,加上一个线性的分析过程,其时间复杂度仍为: ;
- 若不使用基于比较的算法,而是使用计数、基数、桶排序等空间换时间的线性排序算法,那么ThirdMax的时间复杂度为2倍的线性,结果仍然为线性,即为: 。
ThirdMax2的时间复杂度不能直接认定是 ,因为使用了不重复的有序集合,每次添加数据都会导致sorted被重新排序。但是因为sorted中最多只包含3个数字(到达4时被删除1个),所以即便使用了糟糕的 的冒泡,其复杂度也仅为常数 9,即为常量时间内完成排序。在这种情况下ThirdMax2的时间复杂度应该为9倍的线性,其结果仍然为线性,即为: 。
具体的时间复杂度的分析应该具体对待,如果把冒泡的内循环封装成一个方法,便认为冒泡是 那就贻笑大方了。
最新文章
- 转:亿级Web系统的高容错性实践(好博文)
- 实战使用Axure设计App,使用WebStorm开发(5) – 实现页面功能
- 深入理解java虚拟机【内存溢出实例】
- [转]highcharts图表入门之:如何让highcharts图表自适应浏览器窗体的大小或者页面大小
- C++——代码重用
- hdu1025 dp(最长上升子序列LIS)
- centos6.5_x86_64安装Adobe Flash Player
- 《OD大数据实战》Storm环境搭建
- 【转】Android 使用Scroller实现绚丽的ListView左右滑动删除Item效果
- android studio 报ambiguous method call
- 3、手把手教你Extjs5(三)MVVM特性的简单说明
- RedHat Enterprise Linu…
- Python3 tkinter基础 TK title 设置窗体的标题
- SQL的decode()函数
- 设计模式《JAVA与模式》之迭代子模式
- Linux下MySQL安装与操作
- 关于LINQ和SQL操作数据库的性能测试(转)
- js 中 0 和 null 、";"; Boolean 值关系
- 从排序后的结果集中删除 前n条记录
- PLSQL优化基础和性能优化 (学习总结)