在给定的数字组中查找数字频率

Question

假设我们有一个 C++ 中的向量/数组，并且我们希望计算其中 N 个元素中重复出现最多的是哪些，并输出最高计数。哪种算法最适合这项工作？

例如：

int a = { 2, 456, 34, 3456, 2, 435, 2, 456, 2}

输出结果为4，因为数字2出现了4次。这是数字2最大的出现次数。

- Abhishek Mishra

---

我正在使用STL映射填充频率并使用sort(map.begin(),map.end())进行排序，还有更多的速度提升吗？ - Abhishek Mishra

如果问题是“哪个数字”，答案应该是2而不是4 ;-). - Toon Krijthe

@Gamecat 遗憾的是问题是什么频率最大。 - Abhishek Mishra

哦是吗？他们在面试中会问这样的问题吗？我对这种事情毫不知情！！ - Abhishek Mishra

应该是 "int a[] = ..." 吗？ - Alastair

Answer 1

将数组排序，然后快速遍历以计算每个数字的数量。该算法的时间复杂度为O(N*logN)。

或者可以创建一个哈希表，使用数字作为键。在哈希表中存储每个元素对应的计数器。您可以在一次遍历中计算所有元素的数量；然而，该算法的复杂度现在取决于哈希函数的复杂度。

- Franci Penov

---

是的，这正是我所想的。 - Midhat

嗯，是的。现在是凌晨3点，我有一个三周大的宝宝，如果这算作借口的话。 :-) - Franci Penov

没有必要找借口 - 毕竟，SO是一项协作工作 :) - Torsten Marek

为什么使用哈希集而不是树集？这些是数字，更有可能在查找中获得O(logN)。 - Uri

一个哈希表，根据定义，并不能保证唯一性，所以你的第二个方法是行不通的。 - Matt Cruikshank

Answer 2

针对空间优化：

快速排序（例如）然后迭代所有项，仅跟踪最大计数。 最佳情况为O(N log N)。

针对速度优化：

迭代所有元素，跟踪不同计数。 该算法将始终为O(n)。

- Sklivvz

---

如果你进行排序，你只需要保留一个数字序列的最长长度。如果你不排序，你需要在一个关联容器中保留所有数字的计数。 - Torsten Marek

如果您跟踪每个元素的计数，最坏情况将需要N个计数器。您基本上已经将所需内存翻倍了。当然，对于4GB内存机器来说，这不会是一个大问题。但是，对于与操作系统共享的64K内存，您可能需要进行排序。 - Franci Penov

@Franci Penov：整个重点在于-问题是“最佳”，而答案取决于“最佳”的意义。 - Sklivvz

是的，我同意。这就是为什么我提供了两种替代方案 - 排序或计数器哈希表。 :-) 只是想指出第二个算法的内存消耗缺点。内存也很重要，不仅仅是速度。 - Franci Penov

对于“优化速度”的版本来说，更大的问题不是你需要一个大小等于最大可能数的数组来保持O(n)吗？否则，你需要一个O(n*log n)的树或者O(谁知道)的哈希表。 - markets

Answer 3

如果您有足够的内存并且数值不太大，可以使用 计数排序。

- Thorsten79

Answer 4

一个可能利用STL的C++实现如下：

#include <iostream>
#include <algorithm>
#include <map>

// functor
struct maxoccur
{
    int _M_val;
    int _M_rep;

    maxoccur()
    : _M_val(0),
      _M_rep(0)
    {}

    void operator()(const std::pair<int,int> &e)
    {
        std::cout << "pair: " << e.first << " " << e.second << std::endl;
        if ( _M_rep < e.second ) {
            _M_val = e.first;
            _M_rep = e.second;
        }
    }
};

int
main(int argc, char *argv[])
{
    int a[] = {2,456,34,3456,2,435,2,456,2};
    std::map<int,int> m; 

    // load the map
    for(unsigned int i=0; i< sizeof(a)/sizeof(a[0]); i++) 
        m [a[i]]++;

    // find the max occurence...
    maxoccur ret = std::for_each(m.begin(), m.end(), maxoccur());
    std::cout << "value:" << ret._M_val << " max repetition:" << ret._M_rep <<  std::endl;

    return 0;
}

- awgn

Answer 5

哈希算法（构建 count[i] = #occurrences(i) 的时间基本上是线性的）非常实用，但在理论上并不严格满足 O(n)，因为在过程中可能会发生哈希冲突。

这个问题的一个有趣特殊情况是多数元素算法，其中您想要找到一个出现在至少 n/2 个数组条目中的元素（如果存在这样的元素）。

这里有一个快速解释和一个更详细的解释，介绍如何在线性时间内完成此操作，而不需要任何哈希技巧。

- Tyler

Answer 6

一点伪代码：

//split string into array firts
strsplit(numbers) //PHP function name to split a string into it's components
i=0
while( i < count(array))
 {
   if(isset(list[array[i]]))
    {
      list[array[i]]['count'] = list + 1
    }
   else
    {
      list[i]['count'] = 1
      list[i]['number']
    }
   i=i+1
 }
usort(list) //usort is a php function that sorts an array by its value not its key, Im assuming that you have something in c++ that does this
print list[0]['number'] //Should contain the most used number

- Unkwntech

Answer 7

现在，到了2022年，我们有以下新特性：

• 命名空间别名
• 更现代的容器，如std::unordered_map
• CTAD（类模板参数推导）
• 基于范围的for循环
• using语句
• std::ranges库
• 更现代的算法
• 投影
• 结构化绑定

有了这些，我们现在可以写出：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

namespace rng = std::ranges;

int main() {
    // Demo data
    std::vector data{ 2, 456, 34, 3456, 2, 435, 2, 456, 2 };

    // Count values
    using Counter = std::unordered_map<decltype (data)::value_type, std::size_t> ;

    Counter counter{}; for (const auto& d : data) counter[d]++;

    // Get max
    const auto& [value, count] = *rng::max_element(counter, {}, &Counter::value_type::second);

    // Show output
    std::cout << '\n' << value << " found " << count << " times\n";
}

- A M

Answer 8

如果元素的范围与元素数量相比较大，我会像其他人建议的那样，进行排序和扫描。这需要n*log n的时间，而且不需要额外的空间（也许只需要log n的额外空间）。

计数排序的问题在于，如果值的范围很大，初始化计数数组所需的时间可能比排序本身还要长。

- mjcohenw

Answer 9

这将是O(n)的时间复杂度............但问题是大量的数组可以使用相同大小的另一个数组............

for(i=0;i

mar=count[o]; index=o;

for(i=0;i

然后输出将是.........元素index在该数组中出现了max次........

这里a[]是数据数组，我们需要在其中搜索某个数字的最大出现次数......

count[]包含每个元素的计数.......... 注意：我们已经知道数据范围将在数组中。 例如，该数组中的数据范围从1到100.......然后有一个100个元素的计数数组来跟踪，如果它出现，则将索引值增加一........

- kowsalya

Answer 10

这是我完整的、经过测试的版本，使用了 std::tr1::unordered_map。

我将其大致设定为 O(n)。首先，它会遍历 n 个输入值，在unordered_map中插入/更新计数，然后进行partial_sort_copy，这是O(n)的操作。2*O(n) ~= O(n)。

#include <unordered_map>
#include <vector>
#include <algorithm>
#include <iostream>

namespace {
// Only used in most_frequent but can't be a local class because of the member template
struct second_greater {
    // Need to compare two (slightly) different types of pairs
    template <typename PairA, typename PairB>
    bool operator() (const PairA& a, const PairB& b) const
        { return a.second > b.second; }
};
}

template <typename Iter>
std::pair<typename std::iterator_traits<Iter>::value_type, unsigned int>
most_frequent(Iter begin, Iter end)
{
    typedef typename std::iterator_traits<Iter>::value_type value_type;
    typedef std::pair<value_type, unsigned int> result_type;

    std::tr1::unordered_map<value_type, unsigned int> counts;

    for(; begin != end; ++begin)
        // This is safe because new entries in the map are defined to be initialized to 0 for
        // built-in numeric types - no need to initialize them first
        ++ counts[*begin];

    // Only need the top one at this point (could easily expand to top-n)
    std::vector<result_type> top(1);

    std::partial_sort_copy(counts.begin(), counts.end(),
                           top.begin(), top.end(), second_greater());

    return top.front();
}

int main(int argc, char* argv[])
{
    int a[] = { 2, 456, 34, 3456, 2, 435, 2, 456, 2 };

    std::pair<int, unsigned int> m = most_frequent(a, a + (sizeof(a) / sizeof(a[0])));

    std::cout << "most common = " << m.first << " (" << m.second << " instances)" << std::endl;
    assert(m.first == 2);
    assert(m.second == 4);

    return 0;
}

- Alastair