c++ - 找出向量中相同整数的个数

Question

我有一个整数向量。我想在向量中计算相同的整数。我需要一个简单的算法。但是不需要使用太多的标题或内置函数，只需一个简单的算法。非常感谢示例：

std::v={1,1,1,2,2,3} 1:3----2:2----3:1

Answer 1

对它们进行排序，然后计算后面数字的每一个变化。

可选：将计数保存到输出数组。

排序后尝试：

int count = 1;
for(int i = 1; i < v.size(); i++)
{
    if(v[i-1] == v[i])
    {
        count++;
    }
    else
    {
        std::cout << v[i-1] << count << std::endl;
        count = 0;
    }
}
std::cout << v[v.size()-1] << count << std::endl;

Answer 2

至少有两种方法，最常见的解决方案在 O(n log n) 时间内运行，这需要您对数组进行排序，然后遍历它以计算最长的运行时间，如 @yd1 所述。

另一种方法是使用哈希表来生成频率表。这在 O(n) 时间内运行（假设 O(1) 哈希表插入和查找），但由于设置哈希表的开销和需要重新分配哈希表（以及冲突等）的开销，因此对于小的输入向量长度不是最佳的。

您不需要#include <unordered_map>使用哈希表：自己实现一个哈希表是一项本科练习 :) 但是您必须做很多工作才能获得最基本的必要功能。

但是，如果您可以保证向量中的值范围在一些合适的范围内（例如0 <= i < 256），那么您可以使用数组作为映射：

vector<int> values = ...

int table[256] = {0};
for( auto i = values.begin(); i != values.end(); ++i ) {

    assert( 0 <= i && i < 256 );

    table[*i]++;
}

然后迭代table以获取相同的值：

for( size_t i = 0; i < 256; ++i ) {

    if( table[i] > 1 ) cout << i << " appeared " << table[i] << " times." << endl;
}

Answer 3

另一种解决方案是创建从 int 到 int 的附加字典。并将数字（作为键）从向量插入到字典。如果数字存在，那么您应该增加相应给定键的值。

笔记。该字典（地图）保留您向量中整数的出现次数

方法的缺点（从您的角度来看） - 您应该包括地图标题。

这种算法的总体复杂度为 O(N log N)。也许这样的算法会比使用排序更快。您不会使用额外的导线。你有结构，其中包含有关数字出现的信息