leetcode 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

示例 3:

输入:nums = [1,1,1,2,2,2]

输出:5

示例 4:

输入:nums = [10,2,8,9,3,8,1,5,2,3,7,6]

输出:8

提示:

2 <= nums.length <= 10^5

1 <= nums[i] <= 10^5

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/maximum-equal-frequency

二、题解

对于前k个数字组成的数组,如果去掉一个数字后其他数字的出现次数相同,那么这个数组可能是以下几种情况中的一种:

  • 长度为1
  • 所有数字只出现1次,或者只包含某个数字
  • 所有数字的出现次数有1次和x次两种情况,并且出现1次的数字仅有1个
  • 所有数字的出现次数有t和t+1两种情况,并且出现t+1次的数字仅有1个

理清楚以上规则,写代码就不难了。并且需要注意的是,对于前k+1个数字的次数统计情况,我们可以从前k个数字的统计信息中得出。这样只用1次遍历即可完成。

var maxEqualFreq = function(nums) {
    if (nums.length <= 1) return nums.length
    // m 存储某数字出现多少次, t存储出现x次的数组共多少个
    const m = {}, t = {}
    let max = 1
    for (let i = 0; i < nums.length; i++) {
        // 当前数字v, 当前数字出现次数n, 出现n次的数字有c个
        const v = nums[i], n = m[v] || 0, c = t[n]
        // 考虑当前元素,更新统计数据m和t
        c && (--t[n] || delete t[n])
        m[v] = n + 1
        t[n + 1] ? t[n + 1]++ : t[n + 1] = 1
        const keys = Object.keys(t)
        // 三种次数,删除某个数后至少还剩两种次数,不符合
        if (keys.length > 2) continue
        // 所有数字出现次数本身已经相同,去掉某个数字后还相同的情况
        if (keys.length == 1) {
            const time = keys[0], count = t[time]
            // 所有次数都只出现1次,或者某个数字出现多次
            if (time == 1 || count == 1) max = i + 1
        }
        // 两种次数:有一个数仅出现1次,或者两种次数t1, t2相差1并且多者对应数字的数量为1
        if (keys.length == 2) {
            const [t1, t2] = keys
            if (t[1] == 1) max = i + 1
            else if (t1 - t2 == 1 && t[t1] == 1) max = i + 1
            else if (t2 - t1 == 1 && t[t2] == 1) max = i + 1
        }
    }
    return max
};
¥ 赞赏