【hot100】跟着小王一起刷leetcode -- 128. 最长连续序列

2024-02-24 00:52

本文主要是介绍【hot100】跟着小王一起刷leetcode -- 128. 最长连续序列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【hot100】跟着小王一起刷leetcode -- 128. 最长连续序列

  • 128. 最长连续序列
    • 题目解读
    • 关键问题
    • 代码
  • 总结

128. 最长连续序列

题目解读

128. 最长连续序列
在这里插入图片描述
ok,兄弟们,咱们看这个题哈,还是哈希分类下,然后一看题目,居然是中等题,做了一道简单题的我觉得我又可以了,接下来咱们一起看看这个中等题。
在这里插入图片描述
然后读完题之后发现不对了,这。。。。。题目怎么都看不懂呀

看似非常简短的题目,实则好难
在这里插入图片描述
害,那咱也得做呀,一点点看吧

先看下关键的要求哈,只要求时间复杂度是o(n),这是啥意思,这不明摆告诉咱,空间你使劲用,可别不好意思,而且还是哈希分类下,咱想想能不能用hash的方式解决。

首先哈,咱先了解一个事,n,2n,3n都是O(n),也就是n前面那个数只要是固定的,都是O(n)。

了解这个之后咱想一下,这个问题怎么能用空间来换取时间呢?

看题目,咱们知道,就是在找到原数组中能组成最长连续数字序列的长度,啥意思呢?

例如数组是[0,2,3,1,7,4,9],这时候组成的连续的序列有哪些呢?

是不是就是[0,1,2,3,4],也就说原数组中每个数的位置不重要,只要这些数可以组成一个连续的序列即可,然后返回最长序列的长度即可。

关键问题

那我们想一下,怎么入手呢?

首先哈,我们想要达到的效果是O(n),那怎么才能达到O(n)呢?

最好的情况,就是我们一次遍历就能拿到结果,这就是最佳的时间复杂度,但看起来有点困难,那我们把这个时间放宽点,2n,3n或则有限n能不能做到?

这就意味着,我们可以花费n的时间去做一些准备工作,然后再进行处理。

那我们要做什么准备工作呢?

我们从最简单的思想入手,假如这个序列是有序的,那做起来是不是就是很简单,也就是说只需要遍历,一旦出现不连续的部分就代表一个序列的结束,过程中保留最长序列长度即可,但是现在的问题就是该序列并不是有序的。最简单的一个方法就是先排序,然后在进行上述操作就可以,但时间复杂度可能就不大合适了。

然后我试了试排序,没想到,排序更快
在这里插入图片描述

在这里插入图片描述
但本着尝试新办法的心态,咱们还是考虑考虑,怎么可以再不排序的情况下进行类似的操作。

排序之后要做的工作其实就是一点点遍历,然后看看这些数是不是连续的,那不排序能不能也知道该数之后是否还是连续的呢?

答案是可以!

我们首先讲序列中的数字存到map中,key为数字本身的值,value统一设置为1。

这么做的好处是什么呢?

这样我们在遍历原序列的时候可以直接找到该数字之后是否还连续**,例如我现在遍历的是3,我只需要查看4是否在map中,这样就类似于排序之后的效果。遍历完4之后再看看5存在不,依次这样下去,就能知道3起头的序列长度最长有多少了。**

这里有一个小tips,我们在遍历3的时候,已经把3,4,5这一条路走过了,也就是说这时候遍历4的时候并不需要再进行遍历了,因为3的时候已经求出了相对于4起头的序列更长的序列了,此时4,5就没必要在遍历了。就给我们剩下了时间,就直接把map中key为4,5的删除,即可,这样遍历原序列的时候就不需要遍历这俩了。注意遍历3开头的序列结束之后,需要将序列长度存到key为3的value中。

这时候聪明的小伙伴就会说,那如果2是在3之后怎么处理呢?

这也很简单,我们只需要判断3是否存在,并且将其3代表的序列长度直接加到2的value上即可。

重复上述工作,直到完成了原序列的遍历,结果就出来了。

但最后发现时间复杂度干不过排序,就很尴尬,大家有时间的话帮我瞅一眼时间复杂度是多少
在这里插入图片描述

代码

class Solution {public int longestConsecutive(int[] nums) {int maxlength = 0;HashMap<Integer, Integer> integerIntegerHashMap = new HashMap<>();// 将原序列的值存储到map中,方便后续遍历时判断后面是否存在连续的值for (int num : nums) {if (!integerIntegerHashMap.containsKey(num))integerIntegerHashMap.put(num, 1);}for (int num : nums) {int length = 1;int index = num;// 可能存在空值,判断下,防止空指针if(integerIntegerHashMap.get(num)==null)continue;if (integerIntegerHashMap.get(num) == 1) {while (true) {//  这里与上述同理if(integerIntegerHashMap.get(++index)==null)break;if (integerIntegerHashMap.get(index) == 1) {length++;// 遍历过一次,就没必要留着了,直接删掉integerIntegerHashMap.remove(index);} else {// 遍历到value不为1的,直接把他的value加上来就可以,然后停止就可以了length += integerIntegerHashMap.get(index);break;}}integerIntegerHashMap.put(num, length);if (length > maxlength)maxlength = length;}}return maxlength;}public static void main(String[] args) {Solution solution = new Solution();int []p={1,0,-1};System.out.println(solution.longestConsecutive(p));}
}

总结

这个题还可以,不是很简单,我个人感觉,一方面要找到怎么用空间代替原来的排序,另一方面要考虑怎么避免多余的操作。
在这里插入图片描述

这篇关于【hot100】跟着小王一起刷leetcode -- 128. 最长连续序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

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

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L