Элемент с наивысшим результатом в массиве строк

Question

Мне нужно найти элемент с наивысшим вступлением в массив строк. Я не уверен, что делать, поскольку у меня нет большого опыта в этом. Я не знаю указателей/хеш-таблиц.

Я уже сделал это для целых чисел, но я не могу заставить его работать для строк.

Моя версия:

#include <iostream> 
using namespace std; 
int main(int argc, char *argv[]) 
{ 
    int a[]={1,2,3,4,4,4,5}; 
    int n = sizeof(a)/sizeof(int); 
    int *b=new int [n]; 
    fill_n(b,n,0); // Put n times 0 in b 

    int val=0; // Value that is the most frequent 
    for (int i=0;i<n;i++) 
     if(++b[a[i]] >= b[val]) 
      val = a[i]; 

    cout<<val<<endl; 
    delete[] b; 
    return 0; 
    } 

Любая помощь для нахождения наиболее часто встречающийся элемент в массиве строк ценится!

Answer 1

Вы могли бы рассмотреть вопрос об использовании vector строк и использовать map сосчитать вхождений:

#include <iostream> 
#include <vector> 
#include <map> 

using namespace std; 

int main(int argc, char *argv[]) 
{ 
    vector<string> a; 
    map<string, int> m; 

    // fill a with strings 
    a.push_back("a"); 
    a.push_back("b"); 
    a.push_back("b"); 
    a.push_back("c"); 
    a.push_back("c"); 
    a.push_back("c"); 
    a.push_back("d"); 
    a.push_back("e"); 

    // count occurrences of every string 
    for (int i = 0; i < a.size(); i++) 
    { 
     map<string, int>::iterator it = m.find(a[i]); 

     if (it == m.end()) 
     m.insert(pair<string, int>(a[i], 1)); 

     else 
     m[a[i]] += 1; 
    } 

    // find the max 
    map<string, int>::iterator it = m.begin(); 
    for (map<string, int>::iterator it2 = m.begin(); it2 != m.end(); ++it2) 
    { 
     if (it2 -> second > it -> second) 
     it = it2; 
    } 

    cout << it -> first << endl; 
    return 0; 
} 

Это решение, вероятно, не самый лучший с точки зрения элегантности и эффективности, однако она должна дать идею.

Answer 2

Во-первых, рассмотрите использование контейнеров C++, таких как векторы, вместо простых массивов. (Ищите «массив в вектор» или такой, чтобы конвертировать между ними, если вам нужно.)

Тогда, если вы можете использовать C++ 11, вы можете сделать что-то вроде этого (без C++ 11 это станет немного более длительным, но все же выполнимо):

std::string most_occurred(const std::vector<std::string> &vec) { 
    std::map<std::string,unsigned long> str_map; 
    for (const auto &str : vec) 
    ++str_map[str]; 

    typedef decltype(std::pair<std::string,unsigned long>()) pair_type; 

    auto comp = [](const pair_type &pair1, const pair_type &pair2) -> bool { 
    return pair1.second < pair2.second; }; 
    return std::max_element(str_map.cbegin(), str_map.cend(), comp)->first; 
} 

---

Вот версия совместима с более старыми C++

bool comp(const std::pair<std::string,unsigned long> &pair1, 
      const std::pair<std::string,unsigned long> &pair2) { 
    return pair1.second < pair2.second; 
} 

std::string most_occurred(const std::vector<std::string> &vec) { 
    std::map<std::string,unsigned long> str_map; 
    for (std::vector<std::string>::const_iterator it = vec.begin(); 
     it != vec.end(); ++it) 
    ++str_map[*it]; 
    return std::max_element(str_map.begin(), str_map.end(), comp)->first; 
}