【力扣 Hot100】 刷题日记
D3
128.最长连续序列
错解
class Solution {public int longestConsecutive(int[] nums) {Arrays.sort(nums);int maxCnt = 0;int cnt = 0;for (int i = 0; i < nums.length - 1; i++) {if(nums[i] != nums[i + 1] - 1){//如果不连续,取cnt与maxCnt较大值,cnt清零maxCnt = Math.max(cnt, maxCnt);cnt = 0;}else{cnt++;maxCnt = Math.max(cnt, maxCnt);}}return maxCnt = maxCnt != 0 ? maxCnt + 1 : maxCnt;}
}
这里我犯了一个错误,把连续理解为了,索引连续并且元素大小连续。事实上,题目中只需要保证元素大小连续即可,比如1 1 2 2 3
,最大连续长度为3,最先想到的是用Treeset
去重排序,但我看题目提示是哈希表。
TreeSet朴素解法
就是提供两个计数器,记录连续元素的长度以及最大长度,虽然是一次for循环就解决了,但是TreeSet的排序时间复杂度是O(log n),所以总体时间复杂度是O(nlogn),是不符合题意的。
class Solution {public int longestConsecutive(int[] nums) {int cnt = 1; //当前连续长度int maxCnt = 1; //Set<Integer> set = new TreeSet<>();for (int num : nums) {set.add(num);}if(set.isEmpty()) return 0;if(set.size() == 1) return 1;Iterator<Integer> it = set.iterator();int prev = it.next();while(it.hasNext()){int current = it.next();if(current != prev + 1){maxCnt = Math.max(maxCnt, cnt);cnt = 1;}else{cnt++;maxCnt = Math.max(maxCnt, cnt);}prev = current;}return maxCnt;}
}
HashSet解法
这种方法时间复杂度为O(n),符合题意。
思路:
使用set
是为了保证元素不重复,降低时间复杂度,因为题目有说,不要求元素在原序列连续。如果集合中有元素x-1
,那么最长长度一定是从x-1
开始,比如数组1 2 4 6 7 8 9
,如果有6,那么从6开始的序列最长长度就不会从7开始,所以只要统计出从某个元素开始的连续元素的最大值,某个元素到这个最大值的元素数目就是最大值。
代码如下:
class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<>();for(int num : nums){set.add(num);}int ans = 0;for(int x : set){if(set.contains(x-1)){//如果还有更小的连续元素,找最小元素continue;}int y = x + 1;while(set.contains(y)){y++;}ans = Math.max(ans, y - x);//获取最大元素长度}return ans;}}