数组的度python的计数排序 + 哈希

　　Topic

　　给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。

　　你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

　　Example_1

　　输入：[1, 2, 2, 3, 1]

　　输出：2

　　解释：

　　输入数组的度是2，因为元素1和2的出现频数最大，均为2.

　　连续子数组里面拥有相同度的有如下所示:

　　[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]

　　最短连续子数组[2, 2]的长度为2，所以返回2.

　　Example_2

　　输入：[1,2,2,3,1,4,2]

　　输出：6

　　Tips

　　nums.length 在1到 50,000 区间范围内。

　　nums[i] 是一个在 0 到 49,999 范围内的整数。

　　Solution_1

　　第一个思路利用了计数排序的思想

　　首先我们可以利用collections模块下的counter函数

　　求出nums中每个数字出现的次数

　　并求出出现次数最多的次数即原数组最大的度degree

　　之后如果遍历原数字

　　若其对应的degree正是原数组最大的度

　　则不断减小窗口的范围

　　直到其中两侧都逼近到最小范围

　　即两侧都是原数字

　　则说明当前数字对应的最短连续子数组已找到

　　最后若遇到多个最短连续子数组

　　则返回长度最小的最短连续子数组

　　Code_1

　　class Solution:

　　def findShortestSubArray(self, nums: List[int]) -> int:

　　d = collections.Counter(nums)

　　degree = max(d.values())

　　if degree == 1:

　　return 1

　　res = len(nums)

　　for i, j in d.items():

　　if j == degree:

　　start = 0

　　end = len(nums) - 1

　　while nums[start] != i:

　　start += 1

　　while nums[end] != i:

　　end -=1

　　res = min(res, end - start + 1)

　　return res

　　12345678910111213141516171819202122

　　Result_1大连妇科医院哪家好 http://mobile.84211111.cn/

　　Solution_2

　　我们可以利用哈希表方法

　　记录当前数字出现的次数、第一位和最后一位

　　这样就能替代思路一中的逼近的过程

　　首先遍历nums设置字典

　　键为遍历的值

　　键值定义为一个数组

　　数组中第一位为出现的次数

　　第二位位出现的第一次出现的索引

　　第三位为最后一次出现的索引

　　之后可以设置一个度degree和返回结果res

　　当原数字出现次数count比degree大时

　　则将count赋值给degree

　　且最后结果变为窗口长度(end - start + 1)

　　若有多个结果

　　则返回最小的结果

　　Code_2

　　class Solution:

　　def findShortestSubArray(self, nums: List[int]) -> int:

　　mp = {}

　　for i, num in enumerate(nums):

　　if num in mp:

　　mp[num][0] += 1

　　mp[num][2] = i

　　else:

　　mp[num] = [1, i, i]

　　degree = res = 0

　　for count, start, end in mp.values():

　　if degree < count:

　　degree = count

　　res = end - start + 1

　　elif degree == count:

　　if res > end - start + 1:

　　res = end - start + 1

　　return res

　　123456789101112131415161718192021

　　Result_2