Question

697. 数组的度

English Version

题目描述

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

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

 

示例 1：

输入：nums = [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 。

示例 2：

输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：
数组的度是 3 ，因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。

 

提示：

• nums.length 在 1 到 50,000 范围内。
• nums[i] 是一个在 0 到 49,999 范围内的整数。

解法

方法一：哈希表

遍历数组，用哈希表记录数组每个元素出现的次数，以及首次、末次出现的位置。然后遍历哈希表，获取元素出现次数最多（可能有多个）且首末位置差最小的数。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

class Solution:
  def findShortestSubArray(self, nums: List[int]) -> int:
    cnt = Counter(nums)
    degree = cnt.most_common()[0][1]
    left, right = {}, {}
    for i, v in enumerate(nums):
      if v not in left:
        left[v] = i
      right[v] = i
    ans = inf
    for v in nums:
      if cnt[v] == degree:
        t = right[v] - left[v] + 1
        if ans > t:
          ans = t
    return ans

class Solution {
  public int findShortestSubArray(int[] nums) {
    Map<Integer, Integer> cnt = new HashMap<>();
    Map<Integer, Integer> left = new HashMap<>();
    Map<Integer, Integer> right = new HashMap<>();
    int degree = 0;
    for (int i = 0; i < nums.length; ++i) {
      int v = nums[i];
      cnt.put(v, cnt.getOrDefault(v, 0) + 1);
      degree = Math.max(degree, cnt.get(v));
      if (!left.containsKey(v)) {
        left.put(v, i);
      }
      right.put(v, i);
    }
    int ans = 1000000;
    for (int v : nums) {
      if (cnt.get(v) == degree) {
        int t = right.get(v) - left.get(v) + 1;
        if (ans > t) {
          ans = t;
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int findShortestSubArray(vector<int>& nums) {
    unordered_map<int, int> cnt;
    unordered_map<int, int> left;
    unordered_map<int, int> right;
    int degree = 0;
    for (int i = 0; i < nums.size(); ++i) {
      int v = nums[i];
      degree = max(degree, ++cnt[v]);
      if (!left.count(v)) {
        left[v] = i;
      }
      right[v] = i;
    }
    int ans = 1e6;
    for (int v : nums) {
      if (cnt[v] == degree) {
        int t = right[v] - left[v] + 1;
        if (ans > t) {
          ans = t;
        }
      }
    }
    return ans;
  }
};

func findShortestSubArray(nums []int) int {
  cnt := map[int]int{}
  left := map[int]int{}
  right := map[int]int{}
  var degree int
  for i, v := range nums {
    cnt[v]++
    if degree < cnt[v] {
      degree = cnt[v]
    }
    if _, ok := left[v]; !ok {
      left[v] = i
    }
    right[v] = i
  }
  ans := 100000
  for v, c := range cnt {
    if c == degree {
      t := right[v] - left[v] + 1
      if ans > t {
        ans = t
      }
    }
  }
  return ans
}

方法二

func findShortestSubArray(nums []int) (ans int) {
  ans = 50000
  numsMap := make(map[int]int, len(nums))
  for _, num := range nums {
    numsMap[num]++
  }
  var maxDegree int
  for _, num := range numsMap {
    maxDegree = max(num, maxDegree)
  }
  degreeNums := getMaxDegreeElem(maxDegree, numsMap)
  for _, num := range degreeNums {
    f := findSubArray(num, nums)
    ans = min(ans, f)
  }
  return
}

func findSubArray(target int, nums []int) int {
  start := getStartIdx(target, nums)
  end := getEndIdx(target, nums)
  return (end - start) + 1
}

func getStartIdx(target int, nums []int) (start int) {
  for idx, num := range nums {
    if num == target {
      start = idx
      break
    }
  }
  return start
}

func getEndIdx(target int, nums []int) (end int) {
  for i := len(nums) - 1; i > 0; i-- {
    if nums[i] == target {
      end = i
      break
    }
  }
  return
}

func getMaxDegreeElem(maxDegree int, numsMap map[int]int) []int {
  var ans []int
  for key, value := range numsMap {
    if value == maxDegree {
      ans = append(ans, key)
    }
  }
  return ans
}