运维开发网

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

运维开发网 https://www.qedev.com 2021-02-24 09:02 出处:51CTO 作者:ckllf
数组的度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

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号