117 lines
2.9 KiB
Markdown
117 lines
2.9 KiB
Markdown
## 题目地址
|
||
|
||
https://leetcode.com/problems/longest-consecutive-sequence/description/
|
||
|
||
## 题目描述
|
||
|
||
```
|
||
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
|
||
|
||
Your algorithm should run in O(n) complexity.
|
||
|
||
Example:
|
||
|
||
Input: [100, 4, 200, 1, 3, 2]
|
||
Output: 4
|
||
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
|
||
Accepted
|
||
200,786
|
||
Submissions
|
||
485,346
|
||
|
||
```
|
||
|
||
## 思路
|
||
|
||
这是一道最最长连续数字序列长度的题目， 官网给出的难度是`hard`.
|
||
|
||
符合直觉的做法是先排序，然后用一个变量记录最大值，遍历去更新最大值即可，
|
||
|
||
代码：
|
||
|
||
```js
|
||
if (nums.length === 0) return 0;
|
||
let count = 1;
|
||
let maxCount = 1;
|
||
// 这里其实可以不需要排序，这么做只不过是为了方便理解
|
||
nums = [...new Set(nums)].sort((a, b) => a - b);
|
||
for (let i = 0; i < nums.length - 1; i++) {
|
||
if (nums[i + 1] - nums[i] === 1) {
|
||
count++;
|
||
} else {
|
||
if (count > maxCount) {
|
||
maxCount = count;
|
||
}
|
||
count = 1;
|
||
}
|
||
}
|
||
return Math.max(count, maxCount);
|
||
```
|
||
|
||
但是需要排序时间复杂度会上升，题目要求时间复杂度为 O(n),
|
||
那么我们其实可以不用排序去解决的。
|
||
|
||
思路就是将之前”排序之后，通过比较前后元素是否相差 1 来判断是否连续“的思路改为
|
||
不排序而是`直接遍历，然后在内部循环里面查找是否存在当前值的邻居元素`，但是马上有一个
|
||
问题，内部我们`查找是否存在当前值的邻居元素`的过程如果使用数组时间复杂度是 O(n),
|
||
那么总体的复杂度就是 O(n^2)，完全不可以接受。怎么办呢？
|
||
|
||
我们换个思路，用空间来换时间。比如用类似于 hashmap 这样的数据结构优化查询部分，将时间复杂度降低到 O(1), 代码见后面`代码部分`
|
||
|
||
## 关键点解析
|
||
|
||
- 空间换时间
|
||
|
||
## 代码
|
||
|
||
```js
|
||
/*
|
||
* @lc app=leetcode id=128 lang=javascript
|
||
*
|
||
* [128] Longest Consecutive Sequence
|
||
*
|
||
* https://leetcode.com/problems/longest-consecutive-sequence/description/
|
||
*
|
||
* algorithms
|
||
* Hard (40.98%)
|
||
* Total Accepted: 200.3K
|
||
* Total Submissions: 484.5K
|
||
* Testcase Example: '[100,4,200,1,3,2]'
|
||
*
|
||
* Given an unsorted array of integers, find the length of the longest
|
||
* consecutive elements sequence.
|
||
*
|
||
* Your algorithm should run in O(n) complexity.
|
||
*
|
||
* Example:
|
||
*
|
||
*
|
||
* Input: [100, 4, 200, 1, 3, 2]
|
||
* Output: 4
|
||
* Explanation: The longest consecutive elements sequence is [1, 2, 3, 4].
|
||
* Therefore its length is 4.
|
||
*
|
||
*
|
||
*/
|
||
/**
|
||
* @param {number[]} nums
|
||
* @return {number}
|
||
*/
|
||
var longestConsecutive = function(nums) {
|
||
nums = new Set(nums);
|
||
let max = 0;
|
||
let y = 0;
|
||
nums.forEach(x => {
|
||
// 说明x是连续序列的开头元素
|
||
if (!nums.has(x - 1)) {
|
||
y = x + 1;
|
||
while (nums.has(y)) {
|
||
y = y + 1;
|
||
}
|
||
max = Math.max(max, y - x); // y - x 就是从x开始到最后有多少连续的数字
|
||
}
|
||
});
|
||
return max;
|
||
};
|
||
```
|