061. Longest Consecutive Sequence＿时间复杂度

[ender233]

@pezy 你几系出来的，　方法都比较抽象（高效简洁），　前两天每天看一次，都没看懂．　

今天用set实现了下，　再回头看终于明白了．　

如你所说，　直接的思路是排序＋迭代，　无论是map　还是set　都隐含了利用了其自动高效排序的性质优先降低了一次时间复杂度，　如果用了unordered_map，　你还用了默认为０这个性质来去重，　另外加上你用value标识连续数目，直接把代码写成几行了，　赞！

这个issues想和你讨论一下具体的时间复杂度．　每次都不太会分析．

unordered_map 实现：
遍历n， 搜了下map内部机制是用　｀红黑树｀　实现？单次增删改按照｀logn来算，　那么总的时间复杂度是不是：　n*logn` ?　　一个循环内部按照logn的线性时间来算.

　

[pezy]

我是 6 系的。

unordered_map 是哈希表，所以基本操作的复杂度都近似 O(1). 所以我的解法也就是 O(n), 因为有一次遍历。

map 的确是红黑树，insert 操作的确是 O(log n)。