題目

索引從0開始長度為N的陣列A，包含0到N - 1的所有整數。找到最大的集合S並返回其大小，

其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的規則。

假設選擇索引為i的元素A[i]為S的第一個元素，S的下一個元素應該是A[A[i]]，

之後是A[A[A[i]]]... 以此類推，不斷新增直到S出現重複的元素。

示例 1:輸入: A = [5,4,0,3,1,6,2] 輸出: 4

解釋: A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

其中一種最長的 S[K]:

S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

提示：N是[1, 20,000]之間的整數。

A中不含有重複的元素。

A中的元素大小在[0, N-1]之間。

解題思路分析

1、雜湊輔助；時間複雜度O(n)，空間複雜度O(n)

func arrayNesting(nums []int) int {	m := make(map[int]bool)	res := 0	for i := 0; i < len(nums); i++ {		if m[nums[i]] == true {			continue		}		count := 0		cur := i		for {			count++			m[cur] = true			cur = nums[cur]			if cur == i {				break			}		}		if count > res {			res = count		}	}	return res}

2、雜湊輔助；時間複雜度O(n)，空間複雜度O(n)

func arrayNesting(nums []int) int {	m := make(map[int]bool)	res := 0	for i := 0; i < len(nums); i++ {		if m[nums[i]] == true {			continue		}		count := 0		cur := i		for {			count++			m[cur] = true			cur = nums[cur]			if m[cur] == true {				break			}		}		if count > res {			res = count		}	}	return res}

3、遍歷交換；時間複雜度O(n)，空間複雜度O(1)

func arrayNesting(nums []int) int {	res := 0	for i := 0; i < len(nums); i++ {		count := 1		for nums[i] != i {			count++			nums[i], nums[nums[i]] = nums[nums[i]], nums[i]		}		if count > res {			res = count		}	}	return res}

4、並查集；時間複雜度O(n)，空間複雜度O(n)

func arrayNesting(nums []int) int {	res := 0	fa = Init(len(nums))	for i := 0; i < len(nums); i++ {		union(i, nums[i])	}	m := make(map[int]int)	for i := 0; i < len(fa); i++ {		m[find(i)]++	}	for _, v := range m {		if v > res {			res = v		}	}	return res}var fa []int// 初始化func Init(n int) []int {	arr := make([]int, n)	for i := 0; i < n; i++ {		arr[i] = i	}	return arr}// 查詢func find(x int) int {	if fa[x] == x {		return x	}	// 路徑壓縮	fa[x] = find(fa[x])	return fa[x]}// 合併func union(i, j int) {	x, y := find(i), find(j)	if x != y {		fa[x] = y	}}

總結

Medium題目，簡單一些藉助map來判斷是否出現重複，也可以使用並查集