c++ - 在数组中查找模式的最有效方法？

Question

最近想用C找一组数中的众数。当集合较小时，我的代码可以很好地完成。

这是我的代码:

int frequency[10001]; //This array stores the frequency of a number that between 0 to 10000
int main()
{
    int x[10]={1,6,5,99,1,12,50,50,244,50};
    int highest = 0;
    int i,j,k;

    for(i=0;i<10;i++)
    {
        frequency[x[i]]++;
        if(frequency[x[i]]>highest)
            highest = frequency[x[i]];
    }

    printf("The mode in the array : ");
    for(i=0;i<=10001;i++)
        if(frequency[i]==highest)
            printf("%d ",i);
    return 0;
}

后来我发现如果有大量的数字，我的方法会非常慢。此外，如果数字小于 0 或大于 10000，我的程序将无法运行，除非我增加“频率”数组的大小。

因此，我想知道有什么方法可以更有效地找到数组中的模式？谢谢。

Answer 1

使用 hash table . (即 unordered_map 通常是这样实现的)。

您将问题标记为 C++，因此您将获得一些 C++ 示例代码。你自己用 C 实现哈希表。这不是一个糟糕的学习练习。

int x[10]={1,6,5,99,1,12,50,50,244,50};
std::unordered_map<int, int> table; // map of items in "x" to the number of times observed.
for (int i = 0; i < 10; i++)
{
     table[x[i]]++;
}

int mode = 0;
int mode_freq = 0;
for (auto itor = table.begin(); itor != table.end(); itor++)
{
    if (itor->second > mode_freq)
    {
        mode = itor->first;
        mode_freq = itor->second;
    }
}
std::cout << "The mode in the array is " << mode << std::endl;