leetcode刷题记录（四十八）——128. 最长连续序列

（一）问题描述

283. 移动零 - 力扣（LeetCode）283. 移动零 - 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。 示例 1:输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]示例 2:输入: nums = [0]输出: [0] 提示: * 1 <= nums.length <= 104 * -231 <= nums[i] <= 231 - 1 进阶：你能尽量减少完成的操作次数吗？https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked给定一个未排序的整数数组 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

 （二）解决思路

这道题目要求找连续序列，同时不要求序列位置连续，即查找数值大小上连续的元素有几个。那么使用哈希结构中的集合（Set）是最合适的：可以去除数组中重复的元素，又能快速找到符合条件的元素。

思路很简单：

• 找到序列的起始元素（即序列当中数值最小的元素）
• 不断找到该序列中的下一个元素（比当前元素大一），每找到一个，序列长度就加一
• 一个数组里可能包含多个序列，比较得到的多个长度取最大，就是当前数组中的最大连续序列长度。

class Solution {
    public int longestConsecutive(int[] nums) {
        
        //将给定数组转换为集合
        Set<Integer> s=new HashSet<>();
        for(int n : nums){
            s.add(n);
        }

        //用来记录序列长度的变量
        int longestStreak=0;

        //遍历集合中的元素
        for(Integer sn : s){

            //当前已经统计的序列长度，起始时只有一个元素
            int currentStreak=1;

            //当前元素的数值，起始时为当前遍历到的元素sn
            int currentNum=sn;

            //序列当中没有比sn小1的元素，说明sn是一个序列的起始点
            if(!s.contains(sn-1)){   
 
                //只要有比sn大一的元素，就说明序列还没有结束，不断找序列中的下一个元素，同时序列长度加一
                while(s.contains(currentNum+1)){
                    currentStreak+=1;
                    currentNum+=1;
                }

                //取所有序列长度的最大值
                longestStreak=Math.max(longestStreak,currentStreak);
            }
        }

        return longestStreak;
    }
}

 （三）易错点

        这道题要求时间复杂度为O（n），那么就不能有排序，只要针对数组排序，时间复杂度就会大于O（n）。所以这道题解题的关键是想到找序列的起点，以及怎么找序列的节点。如果不找序列的起点，是没有办法按顺序累加元素的。

        另外也不是循环嵌套，时间复杂度就一定大于O(n)的哈。像这道题里面第二层循环的执行是有条件的，时间复杂度还是O(n)。

原文地址：https://blog.csdn.net/weixin_45994787/article/details/145143241

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！