資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告