双哈希表，数次的出现次数种类和数字的最大出现次数 2 种解法，求解《1224. 最大相等频率》
例题
1224. 最大相等频率
给你一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的 最长 前缀，并返回该前缀的长度：
从前缀中 恰好删除一个 元素后，剩下每个数字的出现次数都相同。
如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。
示例 1：
输入：nums = [2,2,1,1,5,3,3,5]
输出：7
解释：对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删去 nums[4] = 5，就可以得到 [2,2,1,1,3,3]，里面每个数字都出现了两次。
示例 2：
输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出：13
提示：
2 <= nums.length <= 105
1 <= nums[i] <= 105
答案
双哈希表 · 数次的出现次数种类
- 数字的出现次数有 2 种
- 1 种比 另 1 种 多，只多出现 1 次
- 1 种只出现 1 次
- 数字的出现次数只 1 种
var maxEqualFreq = function(nums) {
const cnts = new Map, freqs = new Map, n = nums.length
let r = 0
for (let i = 0; i < n; i++) {
const cnt = cnts.get(nums[i]) || 0
cnts.set(nums[i], cnt + 1)
if (freqs.has(cnt)) {
freqs.set(cnt, freqs.get(cnt) - 1)
if (freqs.get(cnt) === 0) freqs.delete(cnt)
}
freqs.set(cnt + 1, (freqs.get(cnt + 1) || 0) + 1)
if (freqs.size === 2) {
const [[ak, av], [bk, bv]] = freqs.entries()
if (av === 1 && (ak === 1 || ak - bk === 1) || bv === 1 && (bk === 1 || bk - ak === 1)) r = Math.max(r, i + 1)
}
}
return cnts.size === n || cnts.size === 1 ? n : r
};双哈希表 · 数字的最大出现次数
数字的出现次数有 2 种
- 1 个数字出现 最大出现次数，其余数字出现 最大出现次数 - 1
- 1 个数字出现 1 次，其余数字出现 最大出现次数
数字的出现次数只 1 种
- 数字的最大出现次数为 1
function maxEqualFreq(nums: number[]): number {
const n = nums.length, cnts = new Map, freqs = new Map
let maxCnt = 0, r = 0
for (let i = 0; i < n; i++) {
const cnt = cnts.get(nums[i]) || 0
cnts.set(nums[i], cnt + 1)
maxCnt = Math.max(maxCnt, cnt + 1)
if (freqs.has(cnt)) freqs.set(cnt, freqs.get(cnt) - 1)
freqs.set(cnt + 1, (freqs.get(cnt + 1) || 0) + 1)
if (maxCnt === 1 || maxCnt + freqs.get(maxCnt - 1) * (maxCnt - 1) === i + 1 || freqs.get(maxCnt) * maxCnt === i) r = Math.max(r, i + 1)
}
return r
};class Solution {
function maxEqualFreq($nums) {
$n = count($nums);
$cnts = array_fill(0, 1e5 + 1, 0);
$freqs = array_fill(0, 1e5 + 1, 0);
$maxCnt = $r = 0;
for ($i = 0; $i < $n; $i++) {
$maxCnt = max($maxCnt, ++$cnts[$nums[$i]]);
$freqs[$cnts[$nums[$i]] - 1]--;
$freqs[$cnts[$nums[$i]]]++;
if ($maxCnt === 1 || $maxCnt + $freqs[$maxCnt - 1] * ($maxCnt - 1) === $i + 1 || $freqs[$maxCnt] * $maxCnt === $i) {
$r = max($r, $i + 1);
}
}
return $r;
}
}func maxEqualFreq(nums []int) int {
cnts, freqs, maxCnt, r := map[int]int{}, map[int]int{}, 0, 0
for i, num := range nums {
cnts[num]++
if maxCnt < cnts[num] {
maxCnt = cnts[num]
}
freqs[cnts[num] - 1]--
freqs[cnts[num]]++
if (maxCnt == 1 || maxCnt + freqs[maxCnt - 1] * (maxCnt - 1) == i + 1 || freqs[maxCnt] * maxCnt == i) {
if r < i + 1 {
r = i + 1
}
}
}
return r
}class Solution {
public int maxEqualFreq(int[] nums) {
Map<Integer, Integer> cnts = new HashMap<Integer, Integer>();
Map<Integer, Integer> freqs = new HashMap<Integer, Integer>();
int n = nums.length, maxCnt = 0, r = 0;
for (int i = 0; i < n; i++) {
int cnt = cnts.getOrDefault(nums[i], 0);
cnts.put(nums[i], cnt + 1);
maxCnt = Math.max(maxCnt, cnt + 1);
freqs.put(cnt, freqs.getOrDefault(cnt, 0) - 1);
freqs.put(cnt + 1,freqs.getOrDefault(cnt + 1, 0) + 1);
if (maxCnt == 1 || maxCnt + freqs.get(maxCnt - 1) * (maxCnt - 1) == i + 1 || freqs.get(maxCnt) * maxCnt == i) {
r = Math.max(r, i + 1);
}
}
return r;
}
}public class Solution {
public int MaxEqualFreq(int[] nums) {
Dictionary<int, int> cnts = new Dictionary<int, int>();
Dictionary<int, int> freqs = new Dictionary<int, int>();
int n = nums.Length, maxCnt = 0, r = 0;
for (int i = 0; i < n; i++) {
if (cnts.ContainsKey(nums[i]) == false) cnts.Add(nums[i], 1);
else cnts[nums[i]]++;
maxCnt = Math.Max(maxCnt, cnts[nums[i]]);
if (freqs.ContainsKey(cnts[nums[i]] - 1)) freqs[cnts[nums[i]] - 1]--;
if (freqs.ContainsKey(cnts[nums[i]]) == false) freqs.Add(cnts[nums[i]], 1);
else freqs[cnts[nums[i]]]++;
if (maxCnt == 1 || maxCnt + freqs.GetValueOrDefault(maxCnt - 1, 0) * (maxCnt - 1) == i + 1 || freqs.GetValueOrDefault(maxCnt, 0) * maxCnt == i) {
r = Math.Max(r, i + 1);
}
}
return r;
}
}#define MAX(a, b) a > b ? a : b
typedef struct {
int key;
int val;
UT_hash_handle hh;
} HashItem;
int maxEqualFreq(int* nums, int numsSize){
HashItem* cnts = NULL;
HashItem* freqs = NULL;
int maxCnt = 0, r = 0;
for (int i = 0; i < numsSize; i++) {
int num = nums[i];
HashItem* pEntry = NULL;
HASH_FIND_INT(cnts, &num, pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = num;
pEntry->val = 1;
HASH_ADD_INT(cnts, key, pEntry);
} else {
pEntry->val += 1;
}
int cnt = pEntry->val - 1;
pEntry = NULL;
HASH_FIND_INT(freqs, &cnt, pEntry);
if (pEntry) pEntry->val -= 1;
cnt++;
maxCnt = MAX(maxCnt, cnt);
pEntry = NULL;
HASH_FIND_INT(freqs, &cnt, pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = cnt;
pEntry->val = 1;
HASH_ADD_INT(freqs, key, pEntry);
} else {
pEntry->val += 1;
}
int freqsMaxCnt = 0;
pEntry = NULL;
HASH_FIND_INT(freqs, &maxCnt, pEntry);
if (pEntry) freqsMaxCnt = pEntry->val;
int freqsMaxCnt1 = 0, maxCnt1 = maxCnt - 1;
pEntry = NULL;
HASH_FIND_INT(freqs, &maxCnt1, pEntry);
if (pEntry) freqsMaxCnt1 = pEntry->val;
if (maxCnt == 1 || maxCnt + maxCnt1 * freqsMaxCnt1 == i + 1 || maxCnt * freqsMaxCnt == i) {
r = MAX(r, i + 1);
}
}
return r;
}class Solution {
public:
int maxEqualFreq(vector<int>& nums) {
unordered_map<int, int> cnts;
unordered_map<int, int> freqs;
int n = nums.size(), maxCnt = 0, r = 0;
for (int i = 0; i < n; i++) {
int cnt = cnts[nums[i]]++;
maxCnt = max(maxCnt, cnt + 1);
freqs[cnt]--;
freqs[cnt + 1]++;
if (maxCnt == 1 || maxCnt + freqs[maxCnt - 1] * (maxCnt - 1) == i + 1 || freqs[maxCnt] * maxCnt == i) {
r = max(r, i + 1);
}
}
return r;
}
};class Solution: # dict 实现
def maxEqualFreq(self, nums: List[int]) -> int:
cnts, freqs, maxCnt, r = dict(), dict(), 0, 0
for i, num in enumerate(nums):
cnt = cnts.get(num, 0)
cnts[num], maxCnt = cnt + 1, max(maxCnt, cnt + 1)
freqs[cnt], freqs[cnt + 1] = freqs.get(cnt, 0) - 1, freqs.get(cnt + 1, 0) + 1
if maxCnt == 1 or maxCnt + freqs.get(maxCnt - 1, 0) * (maxCnt - 1) == i + 1 or freqs.get(maxCnt, 0) * maxCnt == i: r = max(r, i + 1)
return rclass Solution: # list 实现
def maxEqualFreq(self, nums: List[int]) -> int:
cnts, freqs, maxCnt, r = [0] * int(1e5 + 1), [0] * int(1e5 + 1), 0, 0
for i, num in enumerate(nums):
cnts[num] += 1
maxCnt = max(maxCnt, cnts[num])
freqs[cnts[num] - 1] -= 1
freqs[cnts[num]] += 1
if maxCnt == 1 or maxCnt + freqs[maxCnt - 1] * (maxCnt - 1) == i + 1 or freqs[maxCnt] * maxCnt == i: r = max(r, i + 1)
return r