C++计算已排序数组的众数

Question

我需要编写一个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; 

- John

---

如果您不想排序，也可以使用哈希映射。但我仍然不太明白您想问什么。能否提供更多信息？ - gongzhitaao

阅读模式的定义。您想找到最常重复出现的数字。您可以对数字进行排序，然后找到最大公共跨度，或者您可以创建一个直方图，并找到具有最大计数的元素（@gongzhitaao建议使用哈希映射）。这将是O(n)时间和O(n)空间，略优于对数组进行排序。 - ChuckCottrill

counter 不是众数。查看这里 众数。 - gongzhitaao

Answer 1

如果数组已经排序，你可以一次性计算一个数字的出现次数。然后只需保存具有最大出现次数的数字即可。在一个for循环中就可以找到众数。 否则，你将需要做多个for循环。 在下面的链接中查看详细的示例。 如何找到一组数字的众数 这是代码：

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;

- Deidrei

---

谢谢，我觉得这很有用，但是我不得不在else块中交换count和countMode才能使它正常工作。 - 1.618

计数从未增加过。 - Don Larynx

有一个错别字导致逻辑错误：将 countMode++ 改为 count++。 - nmgeek

虽然它能正常工作（除了一个错别字），但仅适用于单一模式。如果存在多个模式，则输出将无法反映出来。任何查看此答案的人都应该意识到这一点，因为您很可能是为了完成作业而在使用此解决方案，但是由于输出无效，即使它看起来是有效的，使用此解决方案也可能被判定为错误。虽然比较复杂，但 @ali 似乎在这篇文章中发布了获取模式的最准确方法。 - Mike

如果模式是数组中的最后一个数字，则无法正常工作。例如：int[] {1,2,3,4,5,5,6,6,6}。 - Parmar Kamlesh

Answer 2

一种方法是使用运行长度编码。在运行长度编码中，表示形式为（Item，其频率）。

在这样做的过程中，要跟踪最大频率和Item。完成运行长度后，这将给您提供模式。

例如：

 1 1  2 2 2 3 3 4 5

它运行长度编码将是：

 {1, 2}, {2, 3}, {3, 2}, {4, 1}, {5, 1}

它需要 O(n) 的空间。

- doptimusprime

Answer 3

这是我的解决方案，它将接受一个已排序的向量作为输入。它具有O(n)的时间复杂度，并且可以处理向量中存在多个“mode”数字的情况。

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;

}

- Anh Nguyen

---

如果模式是数组中的最后一个数字（例如 data = {1,2,3,4,5,5,6,6,6}），则无法正常工作。 - manlio

Answer 4

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;

- Parmar Kamlesh

---

不错，如果模式是数组中的最后一个数字，则这是少数可行的答案之一。当然，它需要一个已排序的数组。 - manlio

Answer 5

这里是代码片段：

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;

- Aseem Baranwal

---

如果模式是数组中的最后一个数字，则不起作用。例如：int[] {1,2,3,4,5,5,6,6,6}，请将 if (count > countMode) { countMode = count; mode = number;} 放在 else 外面。 - Parmar Kamlesh

Answer 6

虽然Diedrei的答案接近正确，但是有几个人指出了一些缺点，例如如果模式由排序数组的最后数字定义（1,2,3,3,4,4,4将返回3作为模式）。此外，根据如何处理多种模式的要求，会有不同的解决方案。

这个解决方案做了几件事情：

1. 解决了模式在数组末尾的问题
2. 如果有多个模式（有多个数字具有相同数量的出现次数，计数>1），则返回最小的数字作为模式
3. 如果没有模式（每个数字仅出现一次），则返回-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;

- STLxZEROx

Answer 7

有一个古老的谚语说：“如果你把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;
}

- Scott A

Answer 8

这段代码用于在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;
}

- ali

Answer 9

我知道这个问题很老了，但是这里有一段干净简短的代码可以计算统计模式：

std::sort(vector.begin(), vector.end());
int mode = vector[0], count = 0, countMode = 1;
int last = mode;
for (int i = 1; i < vector.size(); ++i)
{
    if (vector[i] == mode) ++countMode;
    else
    {
      if (last != vector[i]) count = 0;
      ++count;
    }
    if (count > countMode)
    {
        mode = vector[i];
        countMode = count;
        count = 0;
    }
    last = vector[i];
}

- juan carlos

Answer 10

这段代码应该可以给你提供众数。如果有两个不同的数字出现次数相等，它将输出第一个。

int count = 1, mode = 0, m = 0, i = 1;
size_t sz = sizeof(array)/sizeof(*array);
while(i != sz+1) {
    if(array[i-1] != array[i]) {
        if(count > m) {
            mode = array[i-1];
            m = count;
            count = 1;
        }
    }
    else
        ++count;
    ++i;
}
std::cout << "mode: " << mode << std::endl;

- Mars