128. Longest Consecutive Sequenc

题目

给定一个未排序的数组 nums，返回最长连续数字的长度。
你必须在 O(n) 时间复杂度内解决这个问题。

解析

题目要求的是数组中最长连续元素的个数。所有的排序算法都不可能达到 O(n) 时间复杂度。考虑用空间交换时间的方式。
首先将所有的元素插入到 map 中。然后从这个 map 中获取每一段的连续序列的大小。怎么获取呢？
遍历这个 map 中的每一个元素 num，判断这个元素是不是有 num-1，如果没有的话，可以把这个元素作为起始元素，进行 num+1 的存在判断。更新最大长度。
然后外循环继续迭代，因为如果迭代到 num-1 存在的情况，说明这个点不作为起始点，就不进行内循环。最终在一次遍历这些元素后，就能的到最大值连续长度。

伪代码

m = map[nums]
for num : nums
  if ! m[num-1]
    cur = num
    len = 1
    for ;m[cur+1];
        cur++
        len++
    len=man(len, last)
return last

代码

func longestConsecutive(nums []int) int {
    m := make(map[int]struct{})
    for i  := range nums {
        m[nums[i]] = struct{}{}
    }
    
    rst := 0
    for i := range nums {
        if _, ok1 := m[nums[i] - 1]; !ok1 {
            cur := nums[i]
            length := 1
            
            for ;true; {
                if _, ok2 := m[cur+1]; ok2 {
                    cur++
                    length++
                }else {
                    break
                }
            }
            if length > rst {
                rst = length
            }
        }
    }
    return rst
}

[图片上传中...(image.png-5ff96f-1659318965398-0)]

总结

这道题看了答案，我自己的想法是合并区间，但是发现合并区间比较复杂，应该采用树来进行更简单的和并，后续进行版本改进。