数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的最大相等频率
假设我们有一个包含正整数的数组 nums，我们需要返回给定数组 nums 的数组前缀的最长可能长度，这样就可以从该前缀中删除恰好一个元素，使得其中出现的每个数字都具有相同的频率。如果删除一个元素后没有剩余元素，则仍然认为每个出现的数字都具有相同的频率（0）。
因此，如果输入类似于 [3,3,2,2,6,4,4,6]，则输出将为 7，因此如果我们从索引 4 中删除元素 6，则子数组将为 [3,3,2,2,4,4]，其中所有元素都出现了两次。
为了解决这个问题，我们将遵循以下步骤 -
maxf := 0，res := 0
定义映射 cnt 和 freq
对于初始化 i := 0，当 i < nums 的大小，更新（将 i 增加 1），执行 -
x := nums[i]
（将 cnt[x] 增加 1）
f := cnt[x]
（将 freq[f] 增加 1）
将 freq[f - 1] 减 1
maxf := maxf 和 f 的最大值
如果 maxf * freq[maxf] 等于 i 或 (maxf - 1) * (freq[maxf - 1] + 1) 等于 i 或 maxf 等于 1，则 -
res := i + 1
返回 res
让我们看看以下实现以获得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxEqualFreq(vector<int>& nums) {
int maxf = 0, res = 0;
map<int, int> cnt, freq;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
cnt[x]++;
int f = cnt[x];
freq[f]++;
freq[f - 1]--;
maxf = max(maxf, f);
if (maxf * freq[maxf] == i || (maxf - 1) * (freq[maxf - 1] + 1) == i || maxf == 1) {
res = i + 1;
}
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {3,3,2,2,6,4,4,6};
cout << (ob.maxEqualFreq(v));
}输入
{3,3,2,2,6,4,4,6}输出
7
更新于: 2020年6月4日
205 次查看
广告