最长连续序列(力扣热题HOT100 之 力扣128)Java

简介: 给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

一、题目描述



给定一个未排序的整数数组 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


二、思路讲解



很容易想到:排序后按顺序找等差数列的长度就行了。


需要注意的一点是,如果相邻位置数字相同,则跳过。


三、Java代码实现



class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length<=1){
            return nums.length;
        }
        int count = 1;  //一个等差数列的长度
        int big = 1;  //所有等差数列的最大长度
        Arrays.sort(nums);
        for(int i=0; i<=nums.length-2; i++){
            int temp = nums[i+1]-nums[i];
            if(temp==1){
                count++;
            } else if(temp==0 && count!=1){ //相邻位置数字相同,则直接跳过
            } else {
                big = Math.max(count, big);
                count = 1;
            }
        }
        big = Math.max(count, big);
        return big;
    }
}


时间复杂度:        O(NlogN)

     

空间复杂度:        O(1)


四、思路优化



题目要求算法时间复杂度为 O(n),我们想到使用hash表。hash表查找的时间复杂度为O(1)


将数字全部存入HashSet中,然后依次以每个数为等差数列的末尾,去集合中寻找小1的数字。如果找到,则再-1;如果找不到,则找下一个数字。


但是这样的做法,最坏情况会达到O(N^2)。我们需要进行一些判断。可以注意到,比如我们找的数字是4,然后依次去找3、2、1……,而假如nums中,还有一个3,那么我们还要再去找2、1、0……,事实上,找3以前的数字的这个操作早在找4的时候就已经做过了,就可以直接跳过了。


经过这样的优化,数组中的每个数字其实只被访问过一次,时间复杂度为 O(n)。


五、优化代码



class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }
        int count = 1;  //本次等差数列的长度
        int big = 0;    //所有等差数列的最大长度
        for(int num : nums){
            //如果集合中存在num+1,就放到算num+1的时候去算,这里就不做重复计算了
            if(!set.contains(num+1)){
                int temp = num - 1;
                //不断去找集合中小1的数字
                while(set.contains(temp)){
                    count++;
                    temp--;
                }
                big = Math.max(big, count);
                count = 1;
            }            
        }
        return big;
    }
}


时间复杂度:        O(N)

     

空间复杂度:        O(N)

相关文章
|
4月前
|
Python
【Leetcode刷题Python】376. 摆动序列
文章提供了解决LeetCode "摆动序列" 问题的Python实现代码,通过遍历整数数组并使用两个变量 down 和 up 来记录正差和负差摆动序列的长度,最终返回最长摆动子序列的长度。
42 0
|
2月前
|
算法 Java
LeetCode(一)Java
LeetCode(一)Java
|
4月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
54 6
|
4月前
|
Python
【Leetcode刷题Python】946. 验证栈序列
LeetCode题目“946. 验证栈序列”的Python解决方案,通过模拟栈的压入和弹出操作来验证给定的两个序列是否能通过合法的栈操作得到。
32 6
|
4月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
70 2
|
4月前
|
算法 Python
【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
本文提供了一种Python算法,用以判断给定整数数组是否为某二叉搜索树的后序遍历结果,通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。
23 3
|
4月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
52 1
|
4月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
62 1
|
4月前
|
Python
【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
LeetCode上105号问题"从前序与中序遍历序列构造二叉树"的Python实现,通过递归方法根据前序和中序遍历序列重建二叉树。
30 3
|
4月前
|
算法 Python
【Leetcode刷题Python】300. 最长递增子序列
LeetCode 300题 "最长递增子序列" 的两种Python解决方案:一种使用动态规划,另一种使用贪心算法结合二分查找。
41 1