解题思路
排序+去重
那么这个题目的时间复杂度是O(N^2)
- 首先去重, 这里使用
unordered_set<>, 时间复杂度O(N) - 然后排序, 时间复杂度是O(nlogn)
union find
这个思路需要判断, 如果系统没有这个num, 那么我们就认为这个num很可能是边界.
那么就要查找这个num的左右兄弟姐们
num+1num-1
更新最大值, 这个时候, 我们需要假设几种情况.
-
num将左右两边连起来了,right和left都不为零 -
num连右边 -
num连左边 -
num是孤家寡人一个
class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return len(nums)
map = dict()
ret_max = 0
for num in nums:
if map.has_key(num) != True:
# 表示默认值 0
left = map.get(num-1, 0)
right = map.get(num+1, 0)
new_len = left+right+1
# 只更新三个位置, 就是可能的边界条件
# 因为其他的位置其实都遇到过, 根据我们的策略是不会再次访问到这个数据的.
map[num] = new_len
map[num-left] = new_len
map[num+right] = new_len
ret_max = max(ret_max, new_len)
return ret_max
