LeetCode--128. Longest Consecutive Sequence

本文主要是介绍LeetCode--128. Longest Consecutive Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题链接：https://leetcode.com/problems/longest-consecutive-sequence/

数组中最长连续值子序列，时间复杂度要求O（n）。

没有时间复杂度的要求该问题十分简单。先排序，再遍历一遍计数，时间复杂度为O（nlogn）：

class Solution {public int longestConsecutive(int[] nums) {if (nums == null || nums.length == 0)return 0;Arrays.sort(nums);int max = 1;int count = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] == nums[i-1])continue;else if (nums[i] - nums[i-1] == 1)count++;else {max = Math.max(max, count);count = 1;}}return Math.max(max, count);}
}

有了时间按复杂度的限制就需要一些精巧的数据结构或者tricky的算法，借助HashSet和递归或者迭代来求解，从递归或者迭代的角度看该算法严格来说不是O（n），代码如下：

class Solution {public static HashSet<Integer> set;public static int ret;public int longestConsecutive(int[] nums) {ret=0;set=new HashSet<>();for(int i:nums)set.add(i);for(int i:nums){int tmp=1;int j=i;while(set.contains(j+1)){j++;tmp++;}ret=Math.max(ret,tmp);}return ret;}
}

这里要说明的是，对于AC的测试样例，第二个算法的实际运行效率会低于第一个算法，因为第二个计算hash值要比算法一排序比较大小消耗更多时间。系统无法检测理论时间复杂度，只能根据实际运行时间来检测。

这篇关于LeetCode--128. Longest Consecutive Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---