【leetcode】【2022/8/18】1224. 最大相等频率

问题描述：

• 给你一个正整数数组 nums，从该数组中找出能满足下面要求的最长前缀，并返回该前缀的长度：
  • 从前缀中恰好删除一个元素后，剩下每个数字的出现次数都相同。

核心思路：

• 该题虽然难度标记为困难，但解题思路上并不复杂。
  • 用两个哈希表来记录，第一个哈希表 m1 记录的是数组中出现数值的频数，第二个哈希表 m2 记录的是 m1 中频数的频数，从前往后遍历数组并更新 m1、m2。【注意当 m2 中记录的数值为 0，则将对应键值对删除掉，即假若频数的频数变为 0，则从 m2 中去除掉影响】
    • 简单来说，m1 中的键值对记录的是数值和频数，m2 中的键值对记录的是频数和频数的频数。
  • 想要达到题目的要求（从前缀中恰好删除一个元素后，剩下每个数字的出现次数都相同），则只需要满足 m2 中下面几种情况：
    1. m2.size() == 1，即目前访问的前缀数组中只有一种频数，同时要满足以下两种情况其中一种：
       1. 该频数为 1。【比如前缀数组为 1 2 3 4，此时数组中每个数值的频数均为 1，频数为 1 的频数为 4，此时删除任意一个数值都满足条件】
       2. 假若该频数不为 1，但该频数的频数为 1，也满足条件。【比如前缀数组为 4 4 4，此时此时数组中每个数值的频数为 3，频数为 3 的频数为 1，此时删除任意一个数值都满足条件】
    2. m2.size() == 2，即目前访问的前缀数组中只有两种频数，同时也要满足以下两种情况其中一种：
       1. 其中一个频数为 1 且该频数的频数为 1。【比如前缀数组为 2 3 3 3 4 4 4】
       2. 两个频数相差 1，且更大的频数其频数为 1。【比如前缀数组为 2 2 3 3 4 4 4】
• 该题就很像是在面向示例解题了，把所有情况考虑上就可以了。
  • 实际上该题也仅仅考察了哈希表计数统计，并无很多很难的东西。
• 前面提及的思路是比较直白的思路，如官方题解所示，实际遍历过程中可以维护相应的变量来进行判断（即维护最大的频数以及最小的频数），利用维护的变量进行情况讨论即可。

代码实现：

• 未优化代码实现如下：【不如官方题解简洁，但搭配前面的思路，方便理解题意】

  class Solution
  {
  public:
      int maxEqualFreq(vector<int>& nums)
      {
          unordered_map<int, int> m1;
          map<int, int> m2; // m2有序，为了保证取出来的频数有序
          int len = 0;
          for(int i = 0; i < nums.size(); ++i)
          {
              int num = nums[i];
              if(m1[num] > 0 and --m2[m1[num]] == 0)
                  m2.erase(m1[num]);
              ++m2[++m1[num]];
              auto iter = m2.begin();
              if(m2.size() == 1) // 对应情况 1
              {
                  if(iter->first == 1 or iter->second == 1)
                      len = i+1;
              }
              else if(m2.size() == 2) // 情况 2
              {
                  int a = iter->first; // 最小的频数
                  int c = iter->second; // 最小频数的频数
                  int b = (++iter)->first; // 最大的频数
                  int d = iter->second; // 最大频数的频数
                  if(a == 1 and c == 1) len = i + 1; // 对应情况 2.1
                  else if(b - a == 1 and d == 1) len = i + 1; // 对应情况 2.2
              }
          }
          return len;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33

• 官方题解实现如下：

  class Solution {
  public:
      int maxEqualFreq(vector<int>& nums) {
          unordered_map<int, int> freq, count;
          int res = 0, maxFreq = 0;
          for (int i = 0; i < nums.size(); i++) {
              if (count[nums[i]] > 0) {
                  freq[count[nums[i]]]--;
              }
              count[nums[i]]++;
              maxFreq = max(maxFreq, count[nums[i]]);
              freq[count[nums[i]]]++;
              bool ok = maxFreq == 1 ||
                      freq[maxFreq] * maxFreq + freq[maxFreq - 1] * (maxFreq - 1) == i + 1 && freq[maxFreq] == 1 ||
                      freq[maxFreq] * maxFreq + 1 == i + 1 && freq[1] == 1;
              if (ok) {
                  res = max(res, i + 1);
              }
          }
          return res;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22