网站开发工程师缺口,网站统计数据,网站申请服务器空间,wordpress数字添加链接给定一个未排序的整数数组#xff0c;找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为4
思路#xff1a;map记录某个连续序列端点的最大长度。
对于数字i#xff…给定一个未排序的整数数组找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为4
思路map记录某个连续序列端点的最大长度。
对于数字i如果已经存在跳过。
否则
如果有端点i-1和i1合并。
如果只有一边和本数字合并。
如果相邻数字无端点自己的长度是1
你也可以合并的时候移除报废的端点但是更慢
class Solution {public int longestConsecutive(int[] nums) {if(nums.length0)return 0;MapInteger, Integer mapnew HashMap();int ans1;for(int i:nums){if(!map.containsKey(i)){if(map.containsKey(i-1) map.containsKey(i1)){int lenmap.get(i-1)map.get(i1)1;if(anslen)anslen;map.put(i-1-map.get(i-1)1,len);map.put(i1map.get(i1)-1,len);map.put(i,-1);}else if(map.containsKey(i-1)){int lenmap.get(i-1)1;if(anslen)anslen;map.put(i-1-map.get(i-1)1,len);map.put(i,len);}else if(map.containsKey(i1)){int lenmap.get(i1)1;if(anslen)anslen;map.put(i1map.get(i1)-1,len);map.put(i,len);}else{map.put(i,1);}}}return ans;}
} 我真的不知道还能怎么优化了。
一些小优化基本没用我试过了如果有大变动的做法可以告诉我哈。
