题目:
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
1 2 3
| 输入:nums = [100,4,200,1,3,2] 输出:4 解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
|
示例 2:
1 2
| 输入:nums = [0,3,7,2,5,8,4,6,0,1] 输出:9
|
示例 3:
1 2
| 输入:nums = [1,0,1,2] 输出:3
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> num_set; for (const int& num : nums) { num_set.insert(num); }
int maxLength = 0; int curNum = 0; int curLength = 0; for(const int& num:num_set) { if(!num_set.count(num-1)) { curNum = num; curLength = 1; while(num_set.count(++curNum)) { curLength++; } maxLength = max(maxLength,curLength); } } return maxLength; } };
|
考察的是对set集合的运用