[数据结构与算法] 数据结构与算法之LeetCode-1224. 最大相等频率

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构与算法之LeetCode-1224. 最大相等频率 - 力扣（LeetCode） -> 正文阅读

[数据结构与算法]数据结构与算法之LeetCode-1224. 最大相等频率 - 力扣（LeetCode）

1224. 最大相等频率 - 力扣（LeetCode）

使用哈希表map记录某个数字x出现的次数map[x],freq记录出现次数为f的数的数目为freq[f],maxFreq表示最大出现次数。以某个字符nums[i]结尾的数组前缀合要求的充要条件为满足以下三个条件之一：
- 最大出现次数maxFreq = 1,那么所有数的出现次数都是一次，随意删除一个数即可符合要求
- 所有数的出现次数都是maxFreq或者maxFreq-1，并且最大出现次数的数只有一个，删除一个最大出现次数的数，那么所有数的出现次数都是maxFreq-1
- 除开一个数，其他所有数的出现次数都是maxFreq，并且该数的出现次数为1，直接删除出现次数为1的数，那么所有数的出现次数都是maxFreq

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxEqualFreq = function(nums) {
    const freq = new Map();
    const count = new Map();
    let res = 0, maxFreq = 0;
    for (let i = 0; i < nums.length; i++) {
        if (!count.has(nums[i])) {
            count.set(nums[i], 0);
        }
        if (count.get(nums[i]) > 0) {
            freq.set(count.get(nums[i]), freq.get(count.get(nums[i])) - 1);
        }
        count.set(nums[i], count.get(nums[i]) + 1);
        maxFreq = Math.max(maxFreq, count.get(nums[i]));
        if (!freq.has(count.get(nums[i]))) {
            freq.set(count.get(nums[i]), 0);
        }
        freq.set(count.get(nums[i]), freq.get(count.get(nums[i])) + 1);
        const ok = maxFreq === 1 ||
                freq.get(maxFreq) * maxFreq + freq.get(maxFreq - 1) * (maxFreq - 1) === i + 1 && freq.get(maxFreq) === 1 ||
                freq.get(maxFreq) * maxFreq + 1 === i + 1 && freq.get(1) === 1;
        if (ok) {
            res = Math.max(res, i + 1);
        }
    }
    return res;
};

执行结果：通过

执行用时：140 ms, 在所有 JavaScript 提交中击败了88.89%的用户

内存消耗：51 MB, 在所有 JavaScript 提交中击败了88.89%的用户

通过测试用例：45 / 45

模拟计数

function maxEqualFreq(nums: number[]): number {
    let n = nums.length, max = 0, ans = 0
    const cnt = new Array<number>(100010).fill(0), sum = new Array<number>(100010).fill(0)
    for (let i = 0; i < n; i++) {
        let t = nums[i], len = i + 1, cur = ++cnt[t]
        sum[cur]++; sum[cur - 1]--;
        max = Math.max(max, cur)
        if (max == 1) ans = len
        if (max * sum[max] + 1 == len) ans = len
        if ((max - 1) * (sum[max - 1] + 1) + 1 == len) ans = len
    }
    return ans
};