【C++刷题】力扣-#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 。
题解
为了找到数组中与数组度相同大小的最短连续子数组，我们可以使用以下步骤：
- 计算每个元素的频率： 使用哈希表（或字典）来计算数组中每个元素的出现次数。
- 确定度： 找到频率的最大值，这就是数组的度。
- 找到每个元素的索引： 对于每个元素，记录它在数组中出现的所有索引。
- 计算最短子数组长度： 对于每个频率等于度的元素，计算包含该元素所有出现次数的最短子数组的长度。这可以通过找到该元素最后出现和第一次出现的索引，然后计算这两个索引之间的差值加一来实现。
- 返回最短长度： 在所有频率等于度的元素中，找到最短的子数组长度，并返回这个长度。
代码实现
int findShortestSubArray(vector<int>& nums) {
unordered_map<int, int> count; // 记录每个数字出现的次数
unordered_map<int, vector<int>> positions; // 记录每个数字出现的位置
int degree = 0;
int n = nums.size();
// 计算每个元素的出现次数和位置
for (int i = 0; i < n; ++i) {
int num = nums[i];
count[num]++;
positions[num].push_back(i);
if (count[num] > degree) {
degree = count[num];
}
}
int shortestLength = n;
// 对于每个频率等于度的元素，计算最短子数组的长度
for (auto& pair : count) {
if (pair.second == degree) {
int length = positions[pair.first].back() -
positions[pair.first].front() + 1;
shortestLength = min(shortestLength, length);
}
}
return shortestLength;
}
复杂度分析
● 时间复杂度： O(n)，其中 n 是数组 nums 的长度。我们需要遍历一次数组来构建计数和位置映射。
● 空间复杂度： O(n)，最坏情况下，每个元素都不同，因此我们需要存储 n 个元素的计数和位置信息。