C++ 如何在字符串数组中查找字符串的最大出现次数

Question

我有一个像

这样的字符串数组

{"A", "B", "AA", "ABB", "B", "ABB", "B"}

如何找到在 C++ 中这样的数组中出现次数最多的字符串 ("B")？

谢谢

Answer 1

如果数组元素的类型为 std::string，那么在不使用额外内存资源的情况下，查找数组中出现频率更高的元素的函数可以像演示程序中所示的以下方式下面。

#include <iostream>
#include <string>

size_t max_occurence( const std::string a[], size_t n )
{
    size_t max = 0;
    size_t max_count = 0;
    
    for ( size_t i = 0; i != n; i++ )
    {
        size_t j = 0;
        
        while ( j != i && a[j] != a[i] ) ++j;
        
        if ( j == i )
        {
            size_t count = 1;
            while ( ++j != n )
            {
                if ( a[j] == a[i] ) ++count;
            }
            
            if ( max_count < count )
            {
                max = i;
                max_count = count;
            }
        }
    }
    
    return max;
}

int main() 
{
    std::string a[] = { "A", "B", "AA", "ABB", "B", "ABB", "B" };
    
    auto max = max_occurence( a, sizeof( a ) / sizeof( *a ) );
    
    std::cout << "The most often encountered string is " << a[max] << '\n';

    return 0;
}

程序输出为

The most often encountered string is B

另一种方法是编写通用模板函数。例如

#include <iostream>
#include <string>
#include <functional>
#include <iterator>

template <typename ForwardIterator, 
          typename BinaryPredicate = std::equal_to<typename std::iterator_traits<ForwardIterator>::value_type>>
ForwardIterator max_occurence( ForwardIterator first, 
                               ForwardIterator last, 
                               BinaryPredicate binary_predicate = BinaryPredicate() )
{
    auto max = first;
    typename std::iterator_traits<ForwardIterator>::difference_type max_count = 0;
    
    for ( auto current = first; current != last; ++current )
    {
        auto prev = first;
        
        while ( prev != current && !binary_predicate( *prev, *current ) ) ++prev;
        
        if ( prev == current )
        {
            typename std::iterator_traits<ForwardIterator>::difference_type count = 1;
            
            while ( ++prev != last )
            {
                if ( binary_predicate( *prev, *current ) ) ++count;
            }
            
            if ( max_count < count )
            {
                max = current;
                max_count = count;
            }
        }
    }
    
    return max;
}


int main() 
{
    std::string a[] = { "A", "B", "AA", "ABB", "B", "ABB", "B" };
    
    auto max = max_occurence( std::begin( a ), std::end( a ) );
    
    std::cout << "The most often encountered string is " << *max << '\n';

    return 0;
}

程序输出同上图

The most often encountered string is B

Answer 2

这是一个使用 std::map 的例子。

typedef std::map<std::string, int> Frequency_Map;
int main()
{
  const std::vector<std::string> test_data =
  {
      "A", "B", "AA", "ABB", "B", "ABB", "B",
  };

  Frequency_Map    frequency_table;
  std::string s;
  const size_t length = test_data.length();
  for (unsigned int i = 0; i < length; ++i)
  {
      Frequency_Map::iterator iter(frequency_table.find(test_data[i]);
      if (iter != frequency_table.end())
      {
          ++(iter->second);
      }
      else
      {
          frequency_table[test_data[i]] = 1;
      }
  }

  for (Frequency_Map::iterator iter = frequency_table.begin();
       iter != frequency_table.end();
       ++iter)
  {
      std::cout << iter->first << "    " << iter->second << "\n";
  }
  return 0;
}

上面的代码使用 std::map 构建频率 table，然后输出字符串及其频率。上面的代码可以很容易地修改为找到具有最大（最大）频率的字符串。

C++ 如何在字符串数组中查找字符串的最大出现次数

how to find the maximum occurrence of a string in string array in c++

c++

arrays

string

max

multiple-occurrence