文章目录

• leetcode并查集系列题
• • 128.最长连续序列
  • • 解法一：排序暴力破解
    • 解法二：建立搜索链（并查集思想）

leetcode并查集系列题

此博文主要总结leetcode并查集系列题的解法，由于不熟悉并查集，可能会用其他解法

128.最长连续序列

题目描述

分析

先理解题意，即给一个整数数组，数组内的数是乱序的，现在要求数组的元素能够成连续串(如：1,2,3,4,5,6 或者 10,11,12,13,14)，求连续串的长度最大。

解法一：排序暴力破解

分析

1. 先对数组进行排序，使得数组有序
2. 从数组最小值开始遍历，判断下一个和当前值是不是连续，如果连续则长度加一，如果不连续，相等则继续遍历不初始化长度，若不等则长度重新初始化，继续遍历。

方案分析：

1. 时间消耗主要在于排序，时间复杂度取决于排序算法，后遍历一次的时间复杂度为O(n)
2. O(1)的空间复杂度

代码

func longestConsecutive(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	// 排序数组
	sort.Ints(nums)
	// ret记录结果
	ret := 1
	// n记录每一段连续数据的长度
	n := 1
	for i := 0; i < len(nums)-1; i++ {
		// 下一个等于当前，是重复数据，继续遍历
		if nums[i+1] == nums[i] {
			continue
		}
		// 下一个和当前连续，长度+1
		if nums[i+1] == nums[i]+1 {
			n++
		} else {
			// 初始化长度，ret记录长度最大值
			if ret < n {
				ret = n
			}
			n = 1
		}
	}
	// 有可能存在最后一次长度没有赋值给n，再进行一次判断
	if ret < n {
		ret = n
	}
	return ret
}

解法二：建立搜索链（并查集思想）

分析

可以遍历节点，建立搜索链

1. 建立一个map，扫描一遍数组，则将map[v]=true 达到去重效果
2. 遍历数组，如果 v-1 = true， 循环搜索，确定链长。
3. 返回最短链长

其实搜索链的建立就是并查集的思想

1. 当前节点如果是新节点，且可以加入链，即并入集合
2. 如果是已有节点，不做处理，集合去重复

代码

func longestConsecutive(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
		chain := make(map[int]int)
	for _, v := range nums {
		chain[v] = 1
	}
	// 返回值
	ret := 1
	for _, v := range nums {
        // 判断当前链是否被搜索过，如果被搜索过，继续
		if chain[v] != 1 {
			continue
		}
		_, ok := chain[v-1]
		// 如果不能够接链，那么继续遍历下一个
		if !ok {
			continue
		}
		// 如果当前v-1搜索链不等于1，说明v-1已被搜索过，当前链连到搜索链
		if chain[v-1] != 1 {
			chain[v] += chain[v-1]
		} else {
			// 记录下一个链节点
			next := v-1
			// 当前搜索链存在，但未被搜索过，那么进行搜索
			for ok {
				// 记录以当前节点为起点的链长
				chain[v]++
				// 改变下一个链，表示下一个链已经被访问过
				chain[next]++
				next--
				_, ok = chain[next]
			}
		}
		if ret < chain[v] {
			ret = chain[v]
		}
	}
	return ret
}