0

我可以找到重复次数最多的字符，但找不到第二次重复次数最多的字符

我不明白找到第二个最重复的字符的逻辑

void most_frequent_letter(string str, struct frequents result[])



    int len = str.length();

    int max = 0, i = 0, k = 0, Secmax = 0, m = 0;

for (i = 0 ; i <= len; ++i)
{
    if (str[i] >= 48 && str[i] <= 57)
    {
        result[0].count = 0;
        break;
    }
    if(str[i] >= 65 && str[i] <= 90)
    {
        str[i] += 32;

    }
    result[i].letter = str[i];
    result[i].count++;

    if (result[i].count > max && result[i].letter != ' ')
    {
        max = result[i].count;
        result[0].count = result[i].count;
        result[0].letter = str[i];

    }


}
cout << result[0].letter << endl;
4

4 回答 4

1

这是一个运行良好的示例，如果您愿意，可以对其进行优化。 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <iterator>

void find_most_repeated(std::string strData)
{
    std::map<char, int> mChars;

    for (int i = 0; i < strData.size(); i++)
        mChars[strData[i]] ++;

    std::vector<std::pair<char, int>> v{ std::make_move_iterator(begin(mChars)), std::make_move_iterator(end(mChars)) };

    std::sort(begin(v), end(v), 
        [](const std::pair<char, int>&  p1, const std::pair<char, int>&  p2) {return p1.second > p2.second; });

    std::cout << v[0].first << " " << v[1].first << std::endl;
}

int main()
{
    find_most_repeated(std::string("asdaaaasssaaaaa"));
}
于 2019-07-23T10:50:19.623 回答
1

我认为您可以存储一个字母计数器作为std::map<char, int>示例。然后你只需遍历你的字符串，如果计数器已经包含 current char，你增加它，否则你添加它并将值设置为零。

然后：

  • 搜索最高计数值：您将获得最常见的字母。
  • 擦除地图中的相应元素。
  • 再次搜索最高计数值：您将获得第二频繁的字母。

下面的例子应该更明确：

#include <map>
#include <algorithm>

bool compare(const std::pair<char, int> & a, const std::pair<char, int> & b)
{
    return (a.second < b.second);
}
bool most_frequent_letter(const std::string & str, std::pair<char, char> & results)
{
    if(str.length() >= 2)
    {
        std::map<char, int> counter;

        for(const char & c : str)
            ++counter[c];

        std::map<char, int>::const_iterator it_max = std::max_element(counter.cbegin(), counter.cend(), &compare);
        char c_max = it_max->first;

        counter.erase(it_max);

        it_max = std::max_element(counter.cbegin(), counter.cend(), &compare);
        char c_second = it_max->first;

        results = std::make_pair(c_max, c_second);
        return true;
    }
    else
        return false;
}

该函数most_frequent_letter()接收期望std::string的和std::pair<char, char>对存储字符串中最常见和第二常见的字母的位置的引用。
它返回一个布尔值，其值等于 true 是否可以执行搜索，否则返回 false。

您可以通过以下方式找回它们：

// Create a string
std::string test_string("Hello world");

// Find the two most frequent letters
std::pair <char, char> most_frequents;
bool success = most_frequent_letter(test_string, most_frequents);

// Get them
char most, second_most;
if(success)
{
    most = most_frequents.first;         // first --> most frequent
    second_most = most_frequents.second; // second --> second most frequent
}

我对其进行了测试，并且成功运行。

我试图使这个例子尽可能简单，我希望它会有所帮助。

于 2019-07-23T11:14:09.713 回答
0

后面的细节struct frequents没有给出，但从提供的代码中我猜只isalpha()考虑字母 ( )。
尽管问题中的代码看起来像 C，但它被标记为 C++ 并使用std::string，所以我在这里建议使用 C++ 解决方案。

'a'建议的解决方案使用每个字母（ to ）一个计数器的向量'z'。
第一阶段包括计算句子中每个字母的出现次数（忽略大小写）。
然后找到这个向量中的最大元素给出重复次数最多的字母。
取消相应的计数器后，同一向量中的下一个最大元素给出第二个重复次数最多的字母。

#include <iostream>
#include <string>
#include <cctype>
#include <vector>
#include <algorithm>

std::vector<int> // letter counts
count_letters(const std::string &str)
{
  auto counts=std::vector<int>(1+'z'-'a');
  for(const auto &c: str)
  {
    if(std::isalpha(c))
    {
      ++counts[std::tolower(c)-'a'];
    }
  }
  return counts;
}

int
main()
{
  const auto txt=std::string{"Here is a sentence"};
  auto counts=count_letters(txt);
  const auto max_iter=std::max_element(cbegin(counts), cend(counts));
  const auto max_index=std::distance(cbegin(counts), max_iter);
  std::cout << "max: " << char('a'+max_index)
                       << " (" << counts[max_index] << ")\n";
  counts[max_index]=0; // cancel first max found
  const auto second_max_iter=std::max_element(cbegin(counts), cend(counts));
  const auto second_max_index=std::distance(cbegin(counts), second_max_iter);
  std::cout << "second max: " << char('a'+second_max_index)
                              << " (" << counts[second_max_index] << ")\n";
  return 0;
}

（希望有帮助）

编辑：在没有任何库函数的 C 风格中相同的东西（除了printf()最后），在评论“但我必须在没有算法和 cctype 的情况下这样做”之后


#include <stdio.h>

#define LETTER_COUNT (1+'z'-'a')

void
count_letters(const char *str,
              int *counts)
{
  for(int i=0; str[i]; ++i)
  {
    int c=str[i];
    if((c>='A')&&(c<='Z'))
    {
      c+='a'-'A';
    }
    if((c>='a')&&(c<='z'))
    {
      ++counts[c-'a'];
    }
  }
}

int // index of max count
find_max_index(const int *counts)
{
  int idx=0;
  for(int i=1; i<LETTER_COUNT; ++i)
  {
    if(counts[i]>counts[idx])
    {
      idx=i;
    }
  }
  return idx;
}

int
main(void)
{
  const char *txt="Here is a sentence";
  int counts[LETTER_COUNT]={0};
  count_letters(txt, counts);
  const int max_index=find_max_index(counts);
  printf("max: %c (%d)\n",
         'a'+max_index, counts[max_index]);
  counts[max_index]=0; // cancel first max found
  const int second_max_index=find_max_index(counts);
  printf("second max: %c (%d)\n",
         'a'+second_max_index, counts[second_max_index]);
  return 0;
}
于 2019-07-23T10:47:21.103 回答
0

这是获取字符串中最常见的 2 个字符的一个稍微不同的转折点。由于 astd::map是按键排序的已排序关联容器，请参阅std::map，在创建初始映射后列出 a 中每个字符的频率std::map <char, int>，您可以简单地将成员翻转（即<int, char>并将第一个映射的结果添加到指定std::greater<int>排序（而不是默认std::less<Key>排序顺序）的第二个映射。

例如：

void find_most_repeated (std::string str)
{
    std::map<char, int> mchars;
    std::map<int, char, std::greater<int>> mfreq;
    size_t nmostfreq = 0;

    for (const auto& c : str)           /* fill char/occurrence map */
        mchars[c]++;

    if (mchars.size() < 2) {            /* validate 2 unique chars in str */
        std::cerr << "error: str consists of a single character.\n";
        return;
    }

    for (const auto& pair : mchars)     /* fill sorted occurrence/char map */
        mfreq[pair.second] = pair.first;

    for (const auto& pair : mfreq) {    /* output 2 most frequent chars */
        std::cout << " " << pair.second;
        if (++nmostfreq == 2)
            break;
    }
    std::cout << '\n';
}

添加一个简短的示例（无耻地借用@K.Krunk的示例），您可以这样做：

#include <iostream>
#include <string>
#include <map>

void find_most_repeated (std::string str)
{
    std::map<char, int> mchars;
    std::map<int, char, std::greater<int>> mfreq;
    size_t nmostfreq = 0;

    for (const auto& c : str)           /* fill char/occurrence map */
        mchars[c]++;

    if (mchars.size() < 2) {            /* validate 2 unique chars in str */
        std::cerr << "error: str consists of a single character.\n";
        return;
    }

    for (const auto& pair : mchars)     /* fill sorted occurrence/char map */
        mfreq[pair.second] = pair.first;

    for (const auto& pair : mfreq) {    /* output 2 most frequent chars */
        std::cout << " " << pair.second;
        if (++nmostfreq == 2)
            break;
    }
    std::cout << '\n';
}

int main (void)
{
    find_most_repeated (std::string ("asdaaaasssaaaaa"));
}

示例输出

运行程序将产生第一个和下一个最常见的字符，例如

$ ./bin/chars_most_repeated
 a s

我敢肯定，可能还有十几种方法可以接近它。

于 2019-07-23T13:43:11.233 回答