C++中高效初始化Map为0及数组元素计数优化问询

给定大小为N的数组arr和整数k，统计数组中出现次数超过n/k次的元素数量。

示例输入：

N = 8
arr = [3,1,2,2,1,2,3,3]
k = 4

示例输出：

2

解释：数组中3和2是仅有的出现次数超过8/4=2次的元素。

我目前用C++的map实现统计，先循环初始化所有元素的计数为0，再循环统计次数：

map<int, int> m;
for (int i = 0; i < n; ++i)
{
     m[arr[i]] = 0;
}

for (int i = 0; i < n; ++i)
{
     m[arr[i]] += 1;
}

完整可通过测试用例的代码如下：

//{ Driver Code Starts
// A C++ program to print elements with count more than n/k

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution
{
public:
     // Function to find all elements in array that appear more than n/k times.
     int countOccurence(int arr[], int n, int k)
     {
          // Your code here

          int x = n / k, count = 0;
          map<int, int> m;
          for (int i = 0; i < n; ++i)
          {
               m[arr[i]] = 0;
          }

          for (int i = 0; i < n; ++i)
          {
               m[arr[i]] += 1;
          }

          map<int, int>::iterator it = m.begin();
          while (it != m.end())
          {
               if ((it->second) > x)
                    count += 1;
          }

          return count;
     }
};

//{ Driver Code Starts.
int main()
{
     int t;
     cin >> t;
     while (t--)
     {
          int n, i;
          cin >> n;

          int arr[n];

          for (i = 0; i < n; i++)
               cin >> arr[i];
          int k;
          cin >> k;
          Solution obj;
          cout << obj.countOccurence(arr, n, k) << endl;
     }
     return 0;
}

// } Driver Code Ends

请问有没有更高效的实现方式？比如在单个循环内完成初始化与计数操作？

1. 单循环完成计数（简化现有Map实现） #

你完全不需要单独的初始化循环。C++中，当你访问map中不存在的键时，会自动插入该键并将其值默认初始化为0（对于int类型）。所以可以直接在一个循环里完成计数：

map<int, int> m;
for (int i = 0; i < n; ++i) {
    m[arr[i]]++; // 不存在的键会自动初始化为0，然后加1
}

另外注意你原代码中的一个bug：遍历map的while循环里，迭代器it没有自增（it++），这会导致无限循环，需要修正：

map<int, int>::iterator it = m.begin();
while (it != m.end()) {
    if (it->second > x)
        count++;
    it++; // 必须添加这一行
}

2. 用unordered_map替代map提升效率 #

map底层是红黑树，插入和查找的时间复杂度是O(log n)；而unordered_map是哈希表，平均时间复杂度为O(1)，在数据量较大时性能更优。替换后代码如下：

int countOccurence(int arr[], int n, int k) {
    int x = n / k, count = 0;
    unordered_map<int, int> m;
    for (int i = 0; i < n; ++i) {
        m[arr[i]]++;
    }
    for (auto& pair : m) {
        if (pair.second > x)
            count++;
    }
    return count;
}

这里用范围for循环遍历unordered_map，代码更简洁。

3. 进阶优化：摩尔投票法（空间复杂度O(k)） #

如果追求更低的空间复杂度，可以使用摩尔投票法。核心思路是：最多有k-1个元素能满足出现次数超过n/k次（因为如果有k个这样的元素，总次数会超过n，矛盾）。

步骤如下：

1. 遍历数组，维护一个最多包含k-1个候选元素的哈希表，记录每个候选的计数：
   • 如果当前元素在候选中，计数加1；
   • 如果候选数量小于k-1，添加当前元素并设计数为1；
   • 否则，所有候选计数减1，若计数变为0则移除该候选。
2. 遍历结束后，候选元素可能满足条件，需要再次遍历数组统计它们的真实次数，筛选出符合条件的元素。

实现代码示例：

int countOccurence(int arr[], int n, int k) {
    if (k == 1) return 1; // 所有元素都满足，返回1（数组非空）
    int x = n / k;
    unordered_map<int, int> candidates;

    // 第一阶段：筛选候选元素
    for (int i = 0; i < n; ++i) {
        if (candidates.count(arr[i])) {
            candidates[arr[i]]++;
        } else if (candidates.size() < k - 1) {
            candidates[arr[i]] = 1;
        } else {
            // 所有候选计数减1，移除计数为0的
            vector<int> to_remove;
            for (auto& pair : candidates) {
                pair.second--;
                if (pair.second == 0) {
                    to_remove.push_back(pair.first);
                }
            }
            for (int num : to_remove) {
                candidates.erase(num);
            }
        }
    }

    // 第二阶段：统计候选的真实次数
    unordered_map<int, int> real_counts;
    for (int i = 0; i < n; ++i) {
        if (candidates.count(arr[i])) {
            real_counts[arr[i]]++;
        }
    }

    // 统计符合条件的元素数量
    int count = 0;
    for (auto& pair : real_counts) {
        if (pair.second > x) {
            count++;
        }
    }
    return count;
}

这种方法的时间复杂度是O(nk)，空间复杂度是O(k)，适合k较小的场景，比哈希表的O(n)空间更节省。

内容的提问来源于stack exchange，提问作者Aniruddha