计算c中的重复项

Question

假设我有一个整数数组 {100, 80, 90, 100, 80, 60}

所以我想计算那些重复并保存这些计数器以备后用。因为每个重复的数字都应该除以计数器

像 100 被复制 2 次，所以它们应该是 50。

为了查找重复项，我使用了排序。

 std::sort(array, array + number);
for(int i = 0; i < number; i++) {
  if(array[i] == array[i+1])
    counter++;
}

我试图制作计数器数组以将它们保存在每个数组中。但它没有用。请给我一些更好的主意。

原文由 Hmmmmm 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

方法一

最简单的方法是不对数组进行排序，而是增加地图的元素：

 unordered_map<int, size_t> count;  // holds count of each encountered number
for (int i=0; i<number; i++)
    count[array[i]]++;             // magic !

然后您可以处理地图的内容：

 for (auto &e:count)                // display the result
    cout << e.first <<" : "<<e.second<< "-> "<<e.first/e.second<<endl;

如果需要，通过从地图中重新删除它们或在处理过程中忽略它来过滤掉非重复项。

方法二

如果您不允许使用地图，那么您必须详细说明您的计数循环，以便为每个新数字重新开始计数，并且如果超过两个也能够处理连续的重复：

 ...
for(int i = 0; i < number; i+=counter) {
    for (counter=1; i+counter<number && array[i+counter]==array[i]; )
        counter++;       // count consecutives dups
    if (counter>1) {     // if more than one, process the dups.
        cout << "dup: " << array[i] << " "<<counter<<endl;
    }
}

如果您需要存储对以在第二步中处理它们，则需要存储一对（最好在向量中，但如果需要在数组中）：

 pair<int, size_t> result[number];  // a vector would be preferable
int nres=0;
...
    if (counter>1) {     // if more than one, process the dups.
        // cout << "dup: " << array[i] << " "<<counter<<endl;
        result[nres++] = make_pair(array[i], counter);
    }
...

两种方法的在线演示

原文由 Christophe 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

使用 std::map<int,int> 或 std::unordered_map 来计算出现次数。

然后遍历映射并用键除以原始值（计数器）替换每个值。

最后遍历原始数组并将每个数字替换为其映射值。

如果你使用 std::unordered_map 算法是 O(n)。你原来的 O(n log n) 因为涉及排序。

原文由 Frank Puffer 发布，翻译遵循 CC BY-SA 3.0 许可协议