package degreeofanarray

// 697. 数组的度
// https://leetcode-cn.com/problems/degree-of-an-array/

func findShortestSubArray(nums []int) int {
	ct := make(map[int][2]int, 0)     // 每个数字出现的次数，包括开始、结束位置，0 = 次数
	degreeMax := 0                    // 最大的度
	degreeMap := make(map[int]int, 0) // 这个 degree 里出现的最短路径

	for i, n := range nums {
		o := ct[n]
		if o[0] == 0 {
			ct[n] = [2]int{o[0] + 1, i}
		} else {
			ct[n] = [2]int{o[0] + 1, o[1]}
		}
		degree := o[0] + 1
		if degree > degreeMax {
			degreeMax = degree
		}
		l := i - ct[n][1] + 1
		if degreeMap[degree] == 0 || l < degreeMap[degree] {
			degreeMap[degree] = l
		}
	}
	return degreeMap[degreeMax]
}

func findShortestSubArray2(nums []int) int {

	ct := make(map[int][3]int, 0)     // 每个数字出现的次数，包括开始、结束位置，0 = 次数
	degreeMax := 0                    // 最大的度
	degreeMap := make(map[int]int, 0) // 这个 degree 里出现的最短路径

	for i, n := range nums {
		o := ct[n]
		if o[0] == 0 {
			ct[n] = [3]int{o[0] + 1, i, i}
		} else {
			ct[n] = [3]int{o[0] + 1, o[1], i}
		}
		degree := o[0] + 1
		if degree > degreeMax {
			degreeMax = degree
		}
		l := ct[n][2] - ct[n][1] + 1

		if degreeMap[degree] == 0 || l < degreeMap[degree] {
			degreeMap[degree] = l
		}
	}
	return degreeMap[degreeMax]
}

func findShortestSubArray1(nums []int) int {

	ct := make(map[int][4]int, 0)       // 每个数字出现的次数，包括开始、结束位置，0 = 次数
	degreeMax := 0                      // 最大的度
	degreeMap := make(map[int][]int, 0) // 这个 degree 里出现的所有数字

	for i, n := range nums {
		o := ct[n]
		if o[0] == 0 {
			ct[n] = [4]int{o[0] + 1, i, i, 1}
		} else {
			ct[n] = [4]int{o[0] + 1, o[1], i, i - o[1] + 1}
		}
		degree := o[0] + 1
		if degree > degreeMax {
			degreeMax = degree
		}
		degreeMap[degree] = append(degreeMap[degree], n)
	}
	res := 0
	for _, d := range degreeMap[degreeMax] {
		if res == 0 || ct[d][3] < res {
			res = ct[d][3]
		}
	}
	return res
}