查找最多次出现的数组中的数字

Question

给定一个整数数组,我需要找到最多次出现的数字.我编写了如下算法.

1. 使用地图存储发生的次数和次数.

   map<int, int>

   键:表示数字
   值:表示键发生的次数.

2. 扫描输入数组并使用出现次数和次数更新地图.
3. 从开始到结束迭代地图.找到存在最大值的键.该密钥成为发生次数最多的密钥.

我实现了如下算法.

#include <iostream> 
#include <map>
using namespace std; 
int main()
{
    int a[10] = {1,2,3,2,1,3,2,4,1,1}; //Input array: hardcoded for testing
    map<int, int> m;

    for(int i=0;i<10;i++)
    {
        m[a[i]]++;  //Increment the value of key for counting occurances
    }

    int mostNumTimes = 0; 
    int number = -999; //-999 represents invalid number
    map<int,int>::iterator it = m.begin();
    for( ;it != m.end(); it++)  //Find the number which occurred 
    {                           //most number of times
        if(it->second > mostNumTimes)
        {
            mostNumTimes = it->second;
            number = it->first;
        }
    }
    if(number != -999)   //Print number and number of times it occurred
    {
        cout<<"Number: "<<number<<endl;
        cout<<"Number of times occured: "<<mostNumTimes<<endl;
    }
    else
    {
        cout<<"Input array is empty"<<endl;
    }
    return 0;
}

输出:

1号

发生次数:4

问题:有没有最佳方法？最后,我正在迭代整个地图,因为我找不到任何成员函数来查找其值在地图中最高的键.我可以避免迭代所有键吗？

注意:我没有考虑多个号码是否发生相同的次数.我找到了第一个出现次数最多的号码.

Answer 1

迭代值时,可以保持当前的max(count和int值).在地图中的每个增量上,您可以更新值,这样您就不必在最后进行迭代.

map<int, int> m;
int currentMax = -999;
int maxCount = 0;
for(int i=0;i<10;i++)
{
    int updated = m[a[i]]++;  //Increment the value of key for counting occurances        
    updated++; // due to post increment 
    if (maxCount < updated) {
         maxCount = updated;
         currentMax = i;
    }
}

因为这是一个有趣的练习,似乎我们都假设地图迭代很便宜.虽然迭代地图也是O(N),但它比迭代矢量或数组要昂贵得多.那么什么更便宜,迭代一个可能缩小的大小的地图,或做一个非常基本的检查,将以某个百分比触发两个任务？假设您更改为使用无序映射,那么您的解决方案和此解决方案都是O(N).现在你不是,所以每个插入都是log(n),实际上我认为切换到无序地图将是你最大的收获.