128. 最长连续序列
128. 最长连续序列
题解
题目要求在一个数组中找出一个数字最长连续序列,还要是On
的复杂度
首先把所有数字存在map里面,然后遍历map,此时要对current进行判断,如果hashmap[current-1]存在,那就跳过这次循环,因为我们要去找最小的一个数,如果不存在,这么那个数字必定是某个连续序列中首位数字,这个时候去计数hashmap[current+1]有几个,即可。外层循环需要 O(n)的时间复杂度,只有当一个数是连续序列的第一个数的情况下才会进入内层循环,然后在内层循环中匹配连续序列中的数,因此数组中的每个数只会进入内层循环一次。根据上述分析可知,总时间复杂度为 O(n),符合题目要求。
代码
func longestConsecutive(nums []int) int {
hashmap := make(map[int]bool)
for _, i := range nums {
hashmap[i] = true
}
result := 0
for current := range hashmap {
if !hashmap[current-1] { //不存在比current小的数
current := current
cnt := 1
for hashmap[current+1] {
current++
cnt++
}
if result < cnt {
result = cnt
}
}
}
return result
}