最长的连续元素序列长度

[编程题]最长的连续元素序列长度

热度指数：29565 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个无序的整数类型数组，求最长的连续元素序列的长度。

例如：

给出的数组为[1000, 4, 2000, 1, 3, 2],

最长的连续元素序列为[1, 2, 3, 4]. 返回这个序列的长度：4

你需要给出时间复杂度在O（n）之内的算法

示例1

输入

[1000, 4, 2000, 1, 3, 2]

输出

算法知识视频讲解

华科不平凡

发表于 2020-09-23 18:05:08

采用哈希表存储每个元素，然后遍历整个数组，遍历的时候求当前元素所在连续序列的长度。如[3, 1, 2, 8, 9]，存到哈希表之后，我们遍历这个数组，首先遇到的是3，我们在哈希表中查找3之前的连续数，以及查找3之后的连续数，查完就从哈希表中删除（因为是连续的，所以删除不会影响最终结果），并且更新结展开全文

卫宫士郎红A

发表于 2020-08-23 16:58:58

给定一个无序的整数类型数组，求最长的连续元素序列的长度。例如：给出的数组为[100, 4, 200, 1, 3, 2],最长的连续元素序列为[1, 2, 3, 4]. 返回这个序列的长度：4你需要给出时间复杂度在O（n）之内的算法这道题我想到的有两种做法：1、用一个辅助数组，记录下来数组每个位置对展开全文

北理星星

发表于 2020-08-16 10:44:10

class Solution { public: /** * * @param num int整型vector * @return int整型 */ int longestConsecutive(vector<int>& 展开全文

ButterFlyEffect

发表于 2020-11-08 17:46:01

本题第一时间想到的解法就是排序，但是这样不符合O(n)的时间复杂度要求。另外一种思路就是用一个set记录每个元素的位置，然后遍历数组的元素，对每个元素做向上向下的遍历，统计连续的长度。几个点：1 普通的set查找是O(logN)的，改成hash set就可以认为是O(1)的了。2 在之前序列统计过的展开全文