数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++数组的度
假设我们有一个名为nums的非负整数数组，该数组的度实际上是其任何一个元素的最大频率。我们必须找到nums的具有相同度的连续子数组的最小可能长度。
因此，如果输入类似于[1,2,2,3,1]，则输出将为2，这是因为输入数组的度为2，因为元素1和2都出现两次。具有相同度的子数组 - [1, 2, 2, 3, 1]，[1, 2, 2, 3]，[2, 2, 3, 1]，[1, 2, 2]，[2, 2, 3]，[2, 2] 最短长度为2。所以答案将是2。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个大小为50000的数组freq并将其填充为0
- max_ := 0
- 对于nums中的每个n
- (将freq[n]增加1)
- max_ := max_和freq[n]中的最大值
- 将freq数组填充为0。
- min_ := nums的大小
- 初始化i := 0，j := -1，size := nums的大小，当j < size时，执行：
- 如果j >= 0且freq[nums[j]]与max_相同，则：
- min_ := min_和j - i + 1中的最小值
- 否则，当j < size - 1时，则：
- 将j增加1
- 将freq[nums[j]]增加1
- 否则
- 退出循环
- 如果j >= 0且freq[nums[j]]与max_相同，则：
- 返回min_
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
vector<int> freq(50000, 0);
int max_ = 0;
for (const int n : nums)
max_ = max(max_, ++freq[n]);
fill(freq.begin(), freq.end(), 0);
int min_ = nums.size();
for (int i = 0, j = -1, size = nums.size(); j < size;) {
if (j >= 0 && freq[nums[j]] == max_)
min_ = min(min_, j - i + 1), --freq[nums[i++]];
else if (j < size - 1)
++freq[nums[++j]];
else
break;
}
return min_;
}
};
main(){
Solution ob;
vector<int> v = {1, 2, 2, 3, 1};
cout << (ob.findShortestSubArray(v));
}输入
{1, 2, 2, 3, 1}输出
2
更新于：2020年7月4日
521 次浏览
广告