返回以点C++结束的一行数字中出现次数最多的数字

Question

返回以句点结尾的一行数字中出现次数最多的元素(由用户输入，如：1243253290837993247.(。如果有多个元素满足条件，则返回其中任何一个。C++

我可以找到大多数出现的次数，但无法返回元素本身。此外，我只是一个接一个地输入一行的元素，而不是作为一个输入。。。感谢您的帮助。

顺便说一句，我是一个初学者，所以我想知道只有基本知识的解决方案：(

char count_element(string s)
{
int counter = 0;
int arr[s.size()];
for(int i = 0; i <s.size(); i++)
{
for(int j = i; j < s.size(); j++)
{
if(s[j] == s[i])
{
counter++;
}
}
arr[i] = counter;
}
int M = arr[0];
for(int i = 1; i < s.size(); i++)
{
if(M < arr[i])
M  = arr[i];
}
return '0'; //max occurred element is to be returned```

Answer 1

试试这个：

char getMax(const char* line)
{
int count[10] = {0};
for (int i = 0; line[i] != '.'; i++)
{
int digit = line[i] - '0';
count[digit]++;
}
int index = 0;
for (int i = 1; i < 10; i++)
{
if (count[index] < count[i])
index = i;
}
return '0' + index;
}

Answer 2

我从您发布的代码开始，并对其进行了一些修改，以实现O(1)内存复杂性和O(|s|)时间复杂性。看看这个：

char count_element(string s)
{
int counter = 0;
int count[10] = {0};
int max_occ = 0;
char max_elem = '0';
for(int i = 0; i < s.size() - 1 /* The dot */; i++)
{
int digit = s[i] - '0';
count[digit]++;
if (count[digit] > max_occ)
{
max_occ = count[digit];
max_elem = s[i];
}
}
return max_elem; //max occurred element is to be returned

我希望这能有所帮助。

Answer 3

因此，可以非常简单地将此代码转换为工作代码，只需更改最终循环，这样除了计算出最大计数外，还可以保存具有最大计数的字符。

int M = arr[0];
int C = s[0];
for(int i = 1; i < s.size(); i++)
{
if(M < arr[i])
{
M  = arr[i];
C = s[i];
}
}
return C;

然而，正如Hagen和Mohammed指出的那样，您的代码效率非常低，您可以做得更好。

int arr[s.size()];也是不合法的C++。它是一个可变长度数组(VLA(，但在C++中，数组大小不能是变量，必须是常量。正确的C++代码应该是vector<int> arr(s.size());。但正如哈根所解释的，你其实并不需要这个阵列。

Answer 4

在改进代码之前，您可能需要重新审视您的算法。如果输入的长度是N，则使用大小为O(N)的附加空间arr，然后使用嵌套循环，即O(N²)的运行时。实际上，您只需要计算十位数字中每一位的出现频率，因此您只需要O(1)额外的内存(10个整数的数组(和一个循环(O(N)时间(。

Answer 5

以下使用一些STL算法可能对您有用：

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
char search(std::string const& str) {
std::vector<std::size_t> occurrences;
for (std::size_t i = 0; i < str.find('.'); i++) {
occurrences.push_back(
std::count(str.begin(), str.end(), str[i])
);
}
auto it = std::max_element(occurrences.begin(), occurrences.end());
auto pos = std::distance(occurrences.begin(), it);
return str[pos];
}
int main() {
std::string str{ "124325329083437993247." };
std::cout << search(str) << std::endl; // 3
}