题目链接：https://leetcode.cn/problems/array-nesting/
思路
方法一、并查集
直接想法
这题告诉我们数组内的数字是0-N-1，且不会重复，我们可以把A[i] ， A[A[i]]…看成一个环，数组可以被分成多个环，我们只需计算多个环中的最大长度即可
判断环这里我们用的并查集，把每个元素看成一棵树，将同一个环的A[i] 和A[A[i]]两棵树合并，怎么判断他是同一个环呢？我们只需要去递归走下去，走到他的根节点，判断他们的根节点是否相同即可
算法
1.初始化f数组和size数组，f数组记录当前结点的根节点，初始化都是以自己为根节点，size数组记录每个树的大小
2.find函数用来找当前nums[i]的根节点
3.merge函数用来合并同一环的子树,如果我们同根了表示已经合并过了则直接退出
4.循环遍历nums数组，合并nums[i]和nums[nums[i]]两棵树
代码示例
func arrayNesting(nums []int) int { f := make([]int, len(nums)) size := make([]int, len(nums)) for i := range f{ f[i] = i size[i] = 1 } ans := 1 var find func(x int) int find = func(x int) int{ if x == f[x]{ return x } return find(f[x]) } merge := func(x, y int){ a := find(x) b := find(y) if a == b{ return } f[b] = f[a] size[a] += size[b] if ans < size[a]{ ans = size[a] } } for i := range nums{ merge(nums[i], nums[nums[i]]) } return ans }
复杂度分析
- 时间复杂度：O(n) 其中n表示nums数组的长度，遍历一次nums数组需要O(n)的时间
- 空间复杂度：O(2 * n) 其中n表示nums数组的长度，需要申请f数组和size数组的空间
方法二、标记图
直接想法
遍历数组，从 i 向 nums[i] 连边，我们可以得到一张有向图。
由于题目保证nums 中不含有重复的元素，因此有向图中每个点的出度和入度均为 1。
在这种情况下，有向图必然由一个或多个环组成。我们可以遍历 nums，找到节点个数最大的环。
利用nums 中的元素大小在 [0, n-1] 之间这一条件，我们可以省略 vis 数组，改为标记 nums[i]=n，来实现和 vis 数组同样的功能。
代码示例
func arrayNesting(nums []int) (ans int) { n := len(nums) for i := range nums { cnt := 0 for nums[i] < n { i, nums[i] = nums[i], n cnt++ } if cnt > ans { ans = cnt } } return }
复杂度分析
- 时间复杂度：O(n)，其中 nn 是数组 nums 的长度。
- 空间复杂度：O(1)，我们只需要常数的空间保存若干变量。
