剑指offer-数组篇-最长连续序列-每日练习

• • • 题目描述
    • • [剑指 Offer II 119. 最长连续序列](https://leetcode.cn/problems/WhsWhI/)
    • 分析：
    • 方法一：排序加计数器count
    • 方法二：hashset

难度中等30

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

示例 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 <= 104
• -109 <= nums[i] <= 109

**进阶：**可以设计并实现时间复杂度为 O(n) 的解决方案吗？

• 考虑数组为空的特殊情况

• 遍历时考虑相邻数字相等的情况。如果使用双指针，就需要一个额外的变量记录相等的数字个数，并且将其从end-start的结果里面减出去。

  这里可以分为两个方向：先去重，在遍历，和先遍历，再去重，或者遍历时count不做处理，等于遍历的过程中去重。

• 终止条件：遍历到了数组的最后一个数字

思路：先排序，在进行一次检测。

这里的count初始化为1，默认当前字符已存在于子序列中

 public int longestConsecutive(int[] arr){
         if (arr.length==0){
              return 0;
}
        Arrays.sort(arr);
        int count=1;
        int max=0;
        for (int i = 0; i < arr.length-1; i++) {
            if (arr[i] ==(arr[i+1] -1)){
                count++;
            }else if (arr[i] ==arr[i+1]){
            }else {
                if (count>max)
                    max=count;
                count=1;
            }
        }
        return Math.max(max, count);
    }

执行用时：10 ms, 在所有 Java 提交中击败了99.82%的用户

内存消耗：47.6 MB, 在所有 Java 提交中击败了81.61%的用户

• 使用hashset去重
• 遍历数组
• 如果cur-1在set中，count++。这里默认将遍历的每一个元素当作是子序列的最后一位数，不断探索是否含有比他小的值。
• 比较每一个序列的长度，返回最长的

 public static int longestConsecutive(int[] nums) {
        int count=1;
        int max=0;
        HashSet set=new HashSet();
        //把所有的数字加到set，去重
        for(int i:nums){
            set.add(i);
        }
        for(int cur:nums){
           while(set.contains(cur-1)){
                count++;
                cur=cur-1;
            }
           if(count>max){
               max=count;
           }
           count=1;
        }
        return max;
    }

结果：

超时

分析：

这里数组每一个数字都会去探索一次，但是如果cur已经探索了。那cur-1其实就没有探索的必要了。这里应该进行剪枝

• 所有元素存入hashset；
• 遍历哈希表，若发现比当前元素小1的元素存在于哈希表中，说明此元素不是开头，则跳过。
• 找到开头元素
• 一直递增（每次+1）到hashset中不包含为止。 此为连续序列。

public static int longestConsecutive(int[] nums) {
        int res = 0;
        Set set = new HashSet<>();
        for(int a:nums){
            set.add(a);
        }
        for(int a:nums){
            if(set.contains(a-1)){
                continue;
            }
            int temp = 0;
            while(set.contains(a)){
                a++;
                temp++;
            }
            res = Math.max(res,temp);
        }
        return res;
    }

执行用时：
249 ms, 在所有 Java 提交中击败了22.92%的用户
内存消耗：56 MB 在所有 Java 提交中击败了60.91%的用户