文章目录
1 O ( n l o g n ) O(nlogn) O(nlogn)解法：排序与遍历
如果不考虑题干要求的时间复杂度
O
(
n
)
O(n)
O(n)，那么排序+一次遍历以
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)的解法就可以过。
还是写一下 O ( n l o g n ) O(nlogn) O(nlogn)的解法，原因在最后说。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.size() == 0)
return 0;
sort(nums.begin(), nums.end());
int ans = 1, curr = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] - nums[i - 1] == 1)
curr++;
else if (nums[i] == nums[i - 1]) {
} else {
ans = max(ans, curr);
curr = 1;
}
}
ans = max(ans, curr);
return ans;
}
};
真快。那么
O
(
n
)
O(n)
O(n)的解法会更快吗？
2 O ( n ) O(n) O(n)解法：并查集
小记：unorder_map
我一开始实在想不出 O ( n ) O(n) O(n)，遂看了一眼此题标签，“哈希表”。我看到哈希表便想到map，而map单次操作的复杂度是logn……注意这种条件反射是错误的。下面才是正确的：
unorder_map的本质是hashtable，插入/查找的时间复杂度可视为
O
(
1
)
O(1)
O(1).
而map的本质就是红黑树，插入/查找的时间复杂度为
O
(
l
o
g
n
)
O(logn)
O(logn).
思路
并查集。把已经能串在一串的元素看作一个集合。每个集合中最小的那个数作为根。遍历每个元素，每新增一个元素n，就把n-1所在的那个集合（如果n-1之前出现过）和n+1所在的那个集合（如果n+1之前出现过）以及n合并。hashtable的作用是用O(1)的代价判断n-1和n+1之前是否存在过，以及得到这两个数在nums中的下标。
Q：一个数会不会同时存在与两个集合中？
A：那么这两个集合一定可以合并
class Solution {
unordered_map<int, int> pos;
int root[100010]; // 规定小数为根，根的root值代表该集合的秩（负数以示区分）
int findrt(int ind) // 找出下标为ind的这个数的根
{
if (root[ind] < 0)
return ind;
return root[ind] = findrt(root[ind]);
}
public:
int longestConsecutive(vector<int>& nums) {
memset(root, -1, sizeof(root));
int ans = 0;
for (int i = 0; i < nums.size(); i++) {
if (pos.count(nums[i]) > 0)
continue;
pos[nums[i]] = i;
if (pos.count(nums[i] - 1) > 0) {
// 把nums[i]连到根上
int rt_index = findrt(pos[nums[i] - 1]);
root[rt_index]--; // 秩加1
root[i] = rt_index;
}
if (pos.count(nums[i] + 1) > 0) {
// 此时nums[i]+1一定是根（因为nums[i]第一次出现）
// 把nums[i]+1连到nums[i]的根上
int rt_index = findrt(i);
root[rt_index] += root[pos[nums[i] + 1]];
root[pos[nums[i] + 1]] = rt_index;
}
ans = max(ans, -root[findrt(i)]);
}
return ans;
}
};
这个执行用时实在是尴尬，但是我也想不出优化办法了。方法倒是实实在在的
O
(
n
)
O(n)
O(n)，这个怎么解释呢，测试样例太弱了……？
3 有些差的官解：哈希
官解是这样想的：外层循环遍历每一个元素，对于每一个元素n，我不停的查找n+1、n+2……这一串是否在数组中（事先用unordered_set存下所有的数），记下最长的串长，即为答案。
评论区也有人说了最差情况，就是倒序的串。这样最差时间复杂度就是O(n*n)，还没第一种方法nlogn强了，所以我说这个官解有些差劲。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> num_set;
for (const int& num : nums) {
num_set.insert(num);
}
int longestStreak = 0;
for (const int& num : num_set) {
if (!num_set.count(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.count(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
};
结语
- 本题生动形象的解释了 O ( n l o g n ) O(nlogn) O(nlogn)的运行速度真的不见得比 O ( n ) O(n) O(n)慢。
- 但是本题我认为最好的方法是并查集。