128. Longest Consecutive Sequence

题目

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

题目大意

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 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()，最终输出整个并查集中包含最多元素的那个集合的元素总数。

代码

package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

// 解法一 map，时间复杂度 O(n)
func longestConsecutive(nums []int) int {
	res, numMap := 0, map[int]int{}
	for _, num := range nums {
		if numMap[num] == 0 {
			left, right, sum := 0, 0, 0
			if numMap[num-1] > 0 {
				left = numMap[num-1]
			} else {
				left = 0
			}
			if numMap[num+1] > 0 {
				right = numMap[num+1]
			} else {
				right = 0
			}
			// sum: length of the sequence n is in
			sum = left + right + 1
			numMap[num] = sum
			// keep track of the max length
			res = max(res, sum)
			// extend the length to the boundary(s) of the sequence
			// will do nothing if n has no neighbors
			numMap[num-left] = sum
			numMap[num+right] = sum
		} else {
			continue
		}
	}
	return res
}

// 解法二 并查集
func longestConsecutive1(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	numMap, countMap, lcs, uf := map[int]int{}, map[int]int{}, 0, template.UnionFind{}
	uf.Init(len(nums))
	for i := 0; i < len(nums); i++ {
		countMap[i] = 1
	}
	for i := 0; i < len(nums); i++ {
		if _, ok := numMap[nums[i]]; ok {
			continue
		}
		numMap[nums[i]] = i
		if _, ok := numMap[nums[i]+1]; ok {
			uf.Union(i, numMap[nums[i]+1])
		}
		if _, ok := numMap[nums[i]-1]; ok {
			uf.Union(i, numMap[nums[i]-1])
		}
	}
	for key := range countMap {
		parent := uf.Find(key)
		if parent != key {
			countMap[parent]++
		}
		if countMap[parent] > lcs {
			lcs = countMap[parent]
		}
	}
	return lcs
}

// 解法三 暴力解法，时间复杂度 O(n^2)
func longestConsecutive2(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	numMap, length, tmp, lcs := map[int]bool{}, 0, 0, 0
	for i := 0; i < len(nums); i++ {
		numMap[nums[i]] = true
	}
	for key := range numMap {
		if !numMap[key-1] && !numMap[key+1] {
			delete(numMap, key)
		}
	}
	if len(numMap) == 0 {
		return 1
	}
	for key := range numMap {
		if !numMap[key-1] && numMap[key+1] {
			length, tmp = 1, key+1
			for numMap[tmp] {
				length++
				tmp++
			}
			lcs = max(lcs, length)
		}
	}
	return max(lcs, length)
}

---