【LeetCode】128. 最长连续序列


1.问题

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1

输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2

输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9

提示

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

2.解题思路

2.1 先排序后遍历再判断

先对数组进行升序排列,则若存在连续序列,当遍历到某一值时,其前后之差应该为1,则进行最长序列长度统计;若不为1,如果相等,则跳过此值,进行下一个循环;如果不等,则不连续,当前统计的连续序列长度置为1。见方法longestConsecutive2
此方法,虽然看似时间复杂度为O(N),其实排序就占用了至少O(N),还是不是很理想的算法。

2.2 哈希表

定义一哈希表,key为数组中的元素,value为当前元素所在连续序列的长度。
对于不存在于哈希表中的元素:

  • 取出其左右相邻数已有的连续区间长度 left 和 right
  • 计算当前数的区间长度为:cur_length = left + right + 1
  • 根据 cur_length 更新最大长度 max_length 的值
  • 更新区间两端点的长度值

例如,key = 5, value = 3,意味着对于5来说,有一个长度为3的连续区间,5属于这个区间(不要纠结5这个元素到底在该区间的哪个位置) 具体来说,这个连续区间可能是[4, 6], [3, 5], [5,7]都是满足定义的,具体看nums里有哪些元素。

如果对于元素 num=5,在判断 !map.contains(num) 时,其不存在于哈希表中,即第一次遍历到5这个元素,则对于可能存在的连续序列,num-1若出现在序列当中,则其范围应为[num-value, num-1]. 比如:上述元素5,则4所在范围只能是[4-value, 4],如果不是,那5必在其中,不符合我们的循环条件。这里value表示4所对应的连续序列长度。

同样道理,对于6,其出现的范围只能是[6, 6+value];这里value表示6所对应的连续序列长度。详见代码中方法longestConsecutive

接着需要将之前计算的合并长度进行赋值,并且只要赋值给端点就行了,这是因为整个子序列 [num-left, num+right] 中的元素都已经被访问过了所有的值都已经存储到了map里面,那么如果其他数字想要通过这个判断 !map.contains(num) ,这个数字只可能在这个子序列的左边或者右边.

我们还是以左边为例,当我们放入第num-left-1个数字的时候就需要知道我们的右边第num-left的子序列长度,而通过之前的计算 map[num - left] = cur_length我们可以知道第num-left为开头的最大子序列长度为cur_length, 可以看出左端点(num-left)的值只有其左边的数字用的上,那么他自己自然只需要存右边的子序列长度就可以了,右边同理。

2.3 HashSet

  • 通过HashSet将不重复的元素入库
  • 遍历数组,判断当前num减去1的元素是否已存在:
    • 如果不存在,并且num+当前连续序列最大长度的值存在于HashSet中,统计连续序列长度
    • 否则,跳过该元素。这里循环的条件目的就是找到连续序列的起始元素,找到后,才开始统计最大的连续序列长度

详见代码中方法longestConsecutive3。不过此算法由于用到HashSet,其时间复杂度不符合题目中所需O(N)的条件。

3.代码

class Solution {
    //1.先排序
    //2.连续序列差值为1,统计连续序列长度
    //3.否则,相等的话,继续循环遍历;不等,重新计数连续序列长度
    public int longestConsecutive2(int[] nums) {
        //判空
        if(null==nums || nums.length==0){
            return 0;
        }
        //只有一个
        if(1==nums.length){
            return 1;
        }
        //排序
        Arrays.sort(nums);
        //结果
        int maxLength=1;
        //初始最长连续序列长度
        int current=1;
        for(int i=1;i<nums.length;i++){
            //是否相差1
            if(nums[i]-nums[i-1]==1){
                current++;
                maxLength=Math.max(maxLength, current);
            }
            //相等
            else if(nums[i]==nums[i-1]){
                continue;
            }
            //不等,重新统计
            else{
                current=1;
            }
        }
        return maxLength;
    }


    public int longestConsecutive3(int[] nums) {
        // 遍历数组,构造哈希集合,去重记录出现过的数字
        HashSet<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        int maxLength=0;
        int currentLength=1;
        for(int num : nums){
            //当前数字不是其可能所在连续序列的最小值,则略过;否则向上循环寻找num+1,记录长度
            //如果当前num+当前最大长度不在哈希表里,那这次循环就不用看了
            if(!numSet.contains(num-1) && numSet.contains(num+maxLength)){
                currentLength=1;
                while(numSet.contains(num+1)){
                    currentLength++;
                    num++;
                }
                if(currentLength>maxLength){
                    maxLength=currentLength;
                }
            }
        }
        return maxLength;
    }


    public int longestConsecutive(int[] nums) {
        //定义map为num及其所在连续序列的长度
        Map<Integer, Integer> map=new HashMap<>();
        int left;
        int right;
        int currentLength;
        int maxLength=0;
        for(int num : nums){
            //不包含num
            if(!map.containsKey(num)){
                //对于第一次出现的num, num-1出现的范围只能是[num-left, num-1]
                left=map.getOrDefault(num-1, 0);
                //num+1出现的范围只能是[num+1, num+right]
                right=map.getOrDefault(num+1, 0);
                currentLength=left+right+1;
                if(currentLength>maxLength){
                    maxLength=currentLength;
                }
                //旁边的两个数 我已经相告了,这里对num保存的值不重要
                map.put(num, currentLength);
                //告诉左边的数字我的右边连续子序列长度是curLength(或者说只有他左边的数字需要他)
                map.put(num-left, currentLength);
                //告诉右边的数字我的左边连续子序列长度是cur_length
                map.put(num+right, currentLength);
            }
        }
        return maxLength;
    }
}

文章作者: Kezade
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Kezade !
评论
  目录