每日一题-8th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

---

Leetcode 697. 数组的度

题干

给定一个非空且只包含非负数的整数数组 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。

思路

直接统计法（$O(n^2)$ 时间，$O(n)$ 空间）：建立一个 0~49999 的 char 数组，记录数组中元素出现个数。找到最大值对应的数字，返回原数组中框选。如果想换成 $O(n)$ 时间，那么需要记录所有元素出现的开始端点和结束端点。

实现

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int len = nums.size();
        short* stat = new short[50000] {0};
        int* possibleMaxE = new int[len] {0};
        int pEidx = 0, maxN = 0;
        for (int x : nums) ++stat[x];
        for (int i = 0; i < 50000; ++i) {
            if (stat[i] > maxN) maxN = stat[i];
        }
        for (int i = 0; i < 50000; ++i) {
            if (stat[i] == maxN) {
                possibleMaxE[pEidx] = i;
                ++pEidx;
            }
        }
        delete[] stat;
        int minLen = len;
        for (int i = 0; i < pEidx; ++i) {
            int start = -1; int end = -1;
            for (int j = 0; j < len; ++j) {
                if (nums[j] == possibleMaxE[i]) {
                    if (start == -1) start = j;
                    end = j;
                }
            }
            if (end - start + 1 < minLen)
                minLen = end - start + 1;
        }
        delete[] possibleMaxE;
        return minLen;
    }
};