东莞seo建站咨询wordpress个人博客下载

东莞seo建站咨询,wordpress个人博客下载,营销型网站建设的选择方式,莱芜吧贴吧最新消息思路#xff1a;1.题目要求时间复杂度为O(n)#xff0c;而排序的时间复杂度是O(nlogn)#xff0c;因此本题不能排序。2.核心思路#xff1a;对于nums中的元素x#xff0c;以x为起点#xff0c;不断查找下一个数x 1#xff0c;x 2#xff0c;...是否在nums中#xff…思路1.题目要求时间复杂度为O(n)而排序的时间复杂度是O(nlogn)因此本题不能排序。2.核心思路对于nums中的元素x以x为起点不断查找下一个数x 1x 2...是否在nums中并统计序列的长度。3.为了做到O(n)的时间复杂度需要做到两个关键优化。1把nums中的数都放到一个哈希集合中这样可以以O(1)的时间复杂度判断数字是否在nums中。2如果x - 1在哈希集合中则不以x为起点。这是因为以x - 1为起点计算出的序列长度一定要比以x为起点计算出的序列长度要长这样可以避免大量重复计算。比如nums [3,2,4,5]从3开始可以找到345这个连续序列而从2开始则可以找到2345这个连续序列一定比从3开始找到的连续序列要长。4.注意遍历元素的时候要遍历哈希集合而不是nums。如果nums [1,1,1,...,1,2,3,4,5,...]前一半都是1遍历nums的做法会导致每个1都跑一个O(n)的循环总的循环次数是O(n^2)会超时。附代码class Solution { public int longestConsecutive(int[] nums) { SetInteger set new HashSet(); for(int num : nums){ set.add(num); //把nums转换成哈希集合 } int ans 0; for(int x : set){ //遍历哈希集合 if(set.contains(x - 1)){ //如果x不是序列的起点则直接跳过 continue; } //x是序列的起点 int y x 1; while(set.contains(y)){ //不断查找下一个数是否在哈希集合中 y; } // 循环结束后y - 1就是最后一个在哈希集合中的数 // 长度为 y - 1 - x 1 y - x ans Math.max(ans,y - x); } return ans; } }小优化设m为nums中不同元素的个数即哈希集合的大小。各个连续序列链是相互独立的如果发现其中一条链的长度至少为m/2长度×2m由于不可能还有一条长度大于m/2的链否则这两条链的长度之和就超过m了答案不会再增大此时可以直接返回答案。class Solution { public int longestConsecutive(int[] nums) { SetInteger set new HashSet(); for(int num : nums){ set.add(num); //把nums转换成哈希集合 } int m set.size(); int ans 0; for(int x : set){ //遍历哈希集合 if(set.contains(x - 1)){ //如果x不是序列的起点则直接跳过 continue; } //x是序列的起点 int y x 1; while(set.contains(y)){ //不断查找下一个数是否在哈希集合中 y; } // 循环结束后y - 1就是最后一个在哈希集合中的数 // 长度为 y - 1 - x 1 y - x ans Math.max(ans,y - x); if(ans * 2 m){ break; } } return ans; } }