最长连续序列 秒速五厘米 2022-01-20 00:59 162阅读 0赞 ## 1、问题描述 ## 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。 ## 2、解法 ## ### 2.1 排序 ### 时间复杂度O(n log(n)) public int longestConsecutive(int[] nums) { if(nums==null || nums.length<1) { return 0; } Arrays.sort(nums); int res_count=1; int temp_count =1; for(int i=1;i<nums.length; i++) { if(nums[i] == nums[i-1]+1) { res_count = Math.max(res_count, ++temp_count); }else if (nums[i] != nums[i-1]) { temp_count=1; } } return res_count; } ### 2.2 使用HashSet ### 时间复杂度O(n) public int longestConsecutive(int[] nums) { if(nums==null || nums.length<1) { return 0; } int res_count=1; int temp_count =1; HashSet<Integer> set = new HashSet<Integer>(); for(int num:nums) { set.add(num); } for(int num:nums) { //只需要从最长连续序列的左侧端点开始即可 if(!set.contains(num-1)) { temp_count=1; while(set.contains(++num)) { res_count = Math.max(res_count, ++temp_count); } } } return res_count; }
还没有评论,来说两句吧...