找出向量中相同整数的个数

Question

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

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

Answer 1

Sort 他们，然后计算后面数字的每一个变化。

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

排序后尝试：

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

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

注意。这个字典（地图）保留了你 vector

中整数出现的次数

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

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

Answer 3

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

另一种方法是使用散列table 生成频率table。这运行s 在 O(n) 时间内（假设 O(1) hashtable 插入和查找）但由于设置 hash[=25= 的开销，对于小输入向量长度不是最优的] 并需要重新分配散列table（以及冲突等）。

你不需要#include <unordered_map>来使用散列table：自己实现一个是本科生的练习:)但是你必须做很多跑腿工作才能获得最低限度的必要功能。

但是，如果您可以保证向量中值的范围在某个 suitable 范围内（例如 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;
}

找出向量中相同整数的个数

finding the number of same integers in vector

c++

vector

mod