【力扣 Hot100 | 第六天】4.21(最长连续序列)

2024-04-23 15:52

本文主要是介绍【力扣 Hot100 | 第六天】4.21(最长连续序列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

文章目录

  • 10.最长连续序列
    • 10.1题目
    • 10.2解法:哈希法
      • 10.2.1哈希思路
      • 10.2.2代码实现

10.最长连续序列

10.1题目

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

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

  • 示例一:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
  • 示例二:
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9

10.2解法:哈希法

10.2.1哈希思路

  • 题目要求时间复杂度为O(n)
  • 核心:一次遍历,每个数都判断一次这个数是不是连续序列的开头那个数
    • 用哈希表查找这个数前面一个数是否存在,即num-1在序列中是否存在。存在那这个数肯定不是开头,直接跳过
    • 因此只需要对每个开头的数进行循环,直到这个序列不再连续,因此复杂度是O(n)。
  • 举例:[100,4,200,1,3,4,2] 去重后的哈希序列为:
    [100,4,200,1,3,2]
    按照上面逻辑进行判断:
    • 元素100是开头,因为没有99,且以100开头的序列长度为1
    • 元素4不是开头,因为有3存在,过,
    • 元素200是开头,因为没有199,且以200开头的序列长度为1
    • 元素1是开头,因为没有0,且以1开头的序列长度为4,因为依次累加,2,3,4都存在。
    • 元素3不是开头,因为2存在,过,
    • 元素2不是开头,因为1存在,过。

10.2.2代码实现

	public int longestConsecutive(int[] nums) {if(nums.length==0){return 0;}int res=Integer.MIN_VALUE;Set<Integer> set=new HashSet<>();for(int num:nums){set.add(num);}//1、遍历整个nums数组for(int num:nums){//2、判断 num 是否为有序序列的第一个元素if(set.contains(num-1)==false){//3、num为第一个元素int max=1;while(set.contains(num+1)){num++;max++;}//4、更新最长连续序列长度res=Math.max(res,max);}}return res;}

在这里插入图片描述

这篇关于【力扣 Hot100 | 第六天】4.21(最长连续序列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/929237

相关文章

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查