数据结构与算法之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
};

执行结果：通过

执行用时：80 ms, 在所有 TypeScript 提交中击败了100.00%的用户

内存消耗：55.9 MB, 在所有 TypeScript 提交中击败了100.00%的用户

通过测试用例：45 / 45

参考链接

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

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

【宫水三叶】常规计数模拟题 - 最大相等频率 - 力扣（LeetCode）