C++ 计算有序数组的众数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19920542/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ Calculating the Mode of a Sorted Array
提问by John
I have to write a C++ code that finds the median and mode of an array. I'm told that it's much easier to find the mode of an array AFTER the numbers have been sorted. I sorted the function but still cannot find the mode.
我必须编写一个 C++ 代码来查找数组的中位数和众数。有人告诉我，在数字排序后找到数组的模式要容易得多。我对功能进行了排序，但仍然找不到模式。
int counter = 0;
for (int pass = 0; pass < size - 1; pass++)
for (int count = pass + 1; count < size; count++) {
if (array [count] == array [pass])
counter++;
cout << "The mode is: " << counter << endl;
回答by Deidrei
If the array has been sorted already, you can count the occurrences of a number at once. Then just save the number that has biggest occurrences. And you can find out the mode in only one for-loop. Otherwise, you'll have to do more than one for-loops. See a details example at the link below Find-the-Mode-of-a-Set-of-Numbers
如果数组已经排序，您可以一次计算一个数字的出现次数。然后只需保存出现次数最多的数字。并且您只能在一个 for 循环中找出模式。否则，您将不得不执行多个 for 循环。在下面的链接中查看详细示例 Find-the-Mode-of-a-Set-of-Numbers
Here is the code,
这是代码，
int number = array[0];
int mode = number;
int count = 1;
int countMode = 1;
for (int i=1; i<size; i++)
{
if (array[i] == number)
{ // count occurrences of the current number
++count;
}
else
{ // now this is a different number
if (count > countMode)
{
countMode = count; // mode is the biggest ocurrences
mode = number;
}
count = 1; // reset count for the new number
number = array[i];
}
}
cout << "mode : " << mode << endl;
回答by Aseem Raj Baranwal
Here is the code snippet:
这是代码片段：
int number = array[0];
int mode = number;
int count = 1;
int countMode = 1;
for (int i=1; i<size; i++)
{
if (array[i] == number)
{
count++;
}
else
{
if (count > countMode)
{
countMode = count;
mode = number;
}
count = 1;
number = array[i];
}
}
cout << "mode : " << mode << endl;
回答by doptimusprime
One way is that you can use Run Length encoding. In Run Length encoding, representation would be like; (Item, Its frequency).
一种方法是您可以使用运行长度编码。在运行长度编码中，表示会像；（项目，它的频率）。
While doing so, keep track of the maximum frequency and Item. This will give you the mode once you complete the Run Length.
这样做时，请跟踪最大频率和项目。一旦您完成运行长度，这将为您提供模式。
for example:
例如：
1 1 2 2 2 3 3 4 5
It run length encoding would be
它的运行长度编码将是
{1, 2}, {2, 3}, {3, 2}, {4, 1}, {5, 1}
It needs O(n) space.
它需要 O(n) 空间。
回答by Anh Nguyen
This is how I did it, my solution will take a sorted vector as input. It has O(n) time complexity and can work with the case where there are more than 1 "mode" number in the vector.
我就是这样做的，我的解决方案将采用排序向量作为输入。它具有 O(n) 时间复杂度，并且可以处理向量中有超过 1 个“模式”数的情况。
void findMode(vector<double> data) {
double biggestMode = 1;
vector<double> mode, numbers;
numbers.push_back(data.at(0));
mode.push_back(1);
int count = 0;
for (int i = 1; i < data.size(); i++) {
if (data.at(i) == numbers.at(count)) {
mode.at(count)++;
}
else {
if (biggestMode < mode.at(count)) {
biggestMode = mode.at(count);
}
count++;
mode.push_back(1);
numbers.push_back(data.at(i));
}
}
for (int i = 0; i < mode.size(); i++) {
if (mode.at(i) == biggestMode)
cout << numbers.at(i) << " ";
}
cout << endl;
}
}
回答by Scott A
There is an old adage that states "If you put 10 programmers in a room and give them the same program to code you will get 12 different results", hence my version of answering your question. It may not be as fast (I'm planning on testing it's speed versus some of the other suggestions) but I feel it is easy to understand.
有一句古老的格言说“如果你把 10 个程序员放在一个房间里，并给他们相同的程序来编写代码，你将得到 12 个不同的结果”，因此我的版本回答了你的问题。它可能没有那么快（我计划测试它的速度与其他一些建议的速度）但我觉得它很容易理解。
#include <iostream>
using namespace std;
int main ()
{
short z[10];
short maxCount = 0, curCount = 0, cur = 0, most = 0;
for (int i = 0; i < 10; i++)
{
cout << "Enter a number: " << endl;
cin >> z[i];
}
for (int i = 0; i < 10; i++)
{
cur = z[i];
for (int a = i; a < 10; a++)
{
if (cur == z[a])
{
curCount++;
cur = z[a];
}
if (curCount > maxCount)
{
maxCount = curCount;
most = z[a];
}
}
curCount = 0;
}
cout << "the mode is : " << maxCount << ", the number is: " << most << endl;
}
回答by Parmar Kamlesh
int number = array[0];
int mode = number;
int count = 1;
int countMode = 1;
for (int i=1; i<size; i++)
{
if (array[i] == number)
{ // count occurrences of the current number
++count;
}
else
{ // now this is a different number
count = 1; // reset count for the new number
number = array[i];
}
if (count > countMode) {
countMode = count;
mode = number;
}
}
cout << "mode : " << mode << endl;
回答by STLxZEROx
While Diedrei's answer is close, several people have pointed out some shortcomings such as if the mode is defined by the last numbers of the sorted array (1,2,3,3,4,4,4would return 3 as the mode). Also, depending on the requirements on how to handle multiple modes, there will be different solutions.
虽然 Diedrei 的回答很接近，但有几个人指出了一些缺点，例如模式是否由排序数组的最后一个数字定义（1,2,3,3,4,4,4将返回 3 作为模式）。此外，根据如何处理多种模式的要求，也会有不同的解决方案。
This solution does several things:
这个解决方案做了几件事：
- Solves the issue of the mode being at the end of the array
- If there are multiple modes (more than 1 number has the same number of occurrences with a count > 1), returns the smallest number as the mode
- Returns
-1if there is no mode (each number only occurs once)
- 解决mode在数组末尾的问题
- 如果有多种模式（超过 1 个数字具有相同的出现次数且计数 > 1），则返回最小的数字作为模式
-1如果没有模式则返回（每个数字只出现一次）
int number = array[0];
int mode = number;
int count = 1;
int countMode = 1;
for (int i=1; i<size; i++)
{
if (array[i] == number)
{ // increment the count of occurrences for the current number
++count;
if (count > countMode)
{
countMode = count; // this number now has the most occurrences
mode = number; // this number is now the mode
}
}
else
{ // now this is a different number
count = 1; // reset count for the new number
number = array[i]; // set the new number
}
}
if (countMode == 1) {
mode = -1; // set the mode to -1 if each number in the array occur only once
}
cout << "mode : " << mode << endl;
回答by klestikokona
int findModa(int *arr, int n) {
int count=1;
int countmax=0;
int current = arr[0];
int moda = 0;
for (int i=1; i<n; i++) {
if(arr[i] == curr) {
count++;
}
else if (count>countmax) {
countmax=count;
count=1;
moda=arr[i-1];
current=arr[i];
}
current=arr[i];
}
return moda;
}
回答by ali
This code finds the mode in C++:
此代码在 C++ 中查找模式：
#include <iostream>
using namespace std;
int main(int argc, char** argv)
{
int i,j,k=0,n,repeat_max=0,cn=0;
int array1[50],mode[50],count[50]={0},c[50];
cout<<"\n inter count:\t";
cin>>n;
cout<<"\n";
for(i=0;i<n;i++)
cin>>array1[i];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(array1[i]==array1[j])
{
count[i]++;
if(count[i]>=repeat_max)
{
repeat_max=count[i];
mode[k++]=array1[i];
}
}
}
}
cout<<"\n================\n";
for(i=1;i<k;i++)
cout<<"\t mode[i]="<<mode[i]<<"\n";
cout<<"\t\n\nrepeat array:"<<repeat_max;
return 0;
}
回答by M-J
I did it this way:
我是这样做的：
int main()
{
int mode,modecount2,modecount1;
bool is_nomode=false;
vector<int> numbers = { 15,43,25,25,25,25,16,14,93,93,58,14,55,55,55,64,14,43,14,25,15,56,78,13,15,29,14,14,16 };
sort(numbers);
//If you uncomment the following part, you can see the sorted list of above numbers
//for (int i = 0; i < numbers.size(); ++i) std::cout << numbers[i] << '\n';
//keep_window_open();
mode = numbers[0];
modecount1 = 0;
modecount2 = 1; //Obviously any number exists at least once!
for (int i = 1; i < numbers.size(); ++i) {
if(numbers[i]==numbers[i-1]) ++modecount2;
else {
if (modecount2 > modecount1) {
mode = numbers[i - 1];
modecount1 = modecount2;
}
else if (i != 1 && modecount2 == modecount1) { std::cout << "No mode!\n"; is_nomode = true; break; }
modecount2 = 1;
}
}
if(!is_nomode) std::cout << "Mode of these numbers is: " << mode << std::endl;
keep_window_open();
Also you can add another 25 to the list of numbers and see what happens if two numbers have the same occurrence! I hope it helps.
您也可以将另外 25 添加到数字列表中，看看如果两个数字出现相同会发生什么！我希望它有帮助。
