📑 题目：128. 最长连续序列

🚀 本题 LeetCode 传送门

题目大意

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。

解题思路

  • 给出一个数组，要求找出最长连续序列，输出这个最长的长度。要求时间复杂度为 O(n)。
  • 这一题可以先用暴力解决解决，代码见解法三。思路是把每个数都存在 map 中，先删去 map 中没有前一个数 nums[i]-1 也没有后一个数 nums[i]+1 的数 nums[i]，这种数前后都不连续。然后在 map 中找到前一个数 nums[i]-1 不存在，但是后一个数 nums[i]+1 存在的数，这种数是连续序列的起点，那么不断的往后搜，直到序列“断”了。最后输出最长序列的长度。
  • 这一题最优的解法是解法一，针对每一个 map 中不存在的数 n，插入进去都做 2 件事情。第一件事，先查看 n - 1 和 n + 1 是否都存在于 map 中，如果都存在，代表存在连续的序列，那么就更新 left，right 边界。那么 n 对应的这个小的子连续序列长度为 sum = left + right + 1。第二件事就是更新 left 和 right 左右边界对应的 length = sum。
  • 这一题还可以用并查集解决，见解法二。利用每个数在 nums 中的下标，把下标和下标进行 union()，具体做法是看前一个数 nums[i]-1 和后一个数 nums[i]+1 在 map 中是否存在，如果存在就 union()，最终输出整个并查集中包含最多元素的那个集合的元素总数。

代码

  1. package leetcode
  3. import (
  4.  ""github.com/halfrost/LeetCode-Go/template""
  5. )
  7. // 解法一 map，时间复杂度 O(n)
  8. func longestConsecutive(nums []int) int {
  9.  res, numMap := 0, map[int]int{}
  10.  for _, num := range nums {
  11.   if numMap[num] == 0 {
  12.    left, right, sum := 0, 0, 0
  13.    if numMap[num-1] > 0 {
  14.     left = numMap[num-1]
  15.    } else {
  16.     left = 0
  17.    }
  18.    if numMap[num+1] > 0 {
  19.     right = numMap[num+1]
  20.    } else {
  21.     right = 0
  22.    }
  23.    // sum: length of the sequence n is in
  24.    sum = left + right + 1
  25.    numMap[num] = sum
  26.    // keep track of the max length
  27.    res = max(res, sum)
  28.    // extend the length to the boundary(s) of the sequence
  29.    // will do nothing if n has no neighbors
  30.    numMap[num-left] = sum
  31.    numMap[num+right] = sum
  32.   } else {
  33.    continue
  34.   }
  35.  }
  36.  return res
  37. }
  39. // 解法二 并查集
  40. func longestConsecutive1(nums []int) int {
  41.  if len(nums) == 0 {
  42.   return 0
  43.  }
  44.  numMap, countMap, lcs, uf := map[int]int{}, map[int]int{}, 0, template.UnionFind{}
  45.  uf.Init(len(nums))
  46.  for i := 0; i < len(nums); i++ {
  47.   countMap[i] = 1
  48.  }
  49.  for i := 0; i < len(nums); i++ {
  50.   if _, ok := numMap[nums[i]]; ok {
  51.    continue
  52.   }
  53.   numMap[nums[i]] = i
  54.   if _, ok := numMap[nums[i]+1]; ok {
  55.    uf.Union(i, numMap[nums[i]+1])
  56.   }
  57.   if _, ok := numMap[nums[i]-1]; ok {
  58.    uf.Union(i, numMap[nums[i]-1])
  59.   }
  60.  }
  61.  for key := range countMap {
  62.   parent := uf.Find(key)
  63.   if parent != key {
  64.    countMap[parent]++
  65.   }
  66.   if countMap[parent] > lcs {
  67.    lcs = countMap[parent]
  68.   }
  69.  }
  70.  return lcs
  71. }
  73. // 解法三 暴力解法，时间复杂度 O(n^2)
  74. func longestConsecutive2(nums []int) int {
  75.  if len(nums) == 0 {
  76.   return 0
  77.  }
  78.  numMap, length, tmp, lcs := map[int]bool{}, 0, 0, 0
  79.  for i := 0; i < len(nums); i++ {
  80.   numMap[nums[i]] = true
  81.  }
  82.  for key := range numMap {
  83.   if !numMap[key-1] && !numMap[key+1] {
  84.    delete(numMap, key)
  85.   }
  86.  }
  87.  if len(numMap) == 0 {
  88.   return 1
  89.  }
  90.  for key := range numMap {
  91.   if !numMap[key-1] && numMap[key+1] {
  92.    length, tmp = 1, key+1
  93.    for numMap[tmp] {
  94.     length++
  95.     tmp++
  96.    }
  97.    lcs = max(lcs, length)
  98.   }
  99.  }
  100.  return max(lcs, length)
  101. }

**