c++ - 恒定大小数组的运行中位数

Question

我正在尝试找到恒定大小数组的中位数。但是数组总是在更新。我的意思是新号码被旧号码取代。我称此过程为运行中位数，或者我们可以说是动态中位数。这是我的代码，在代码内部，当 rand() 函数生成 78 时，代码无法找到正确的中位数。 (78之前；生成了41、67、34、0、69、24)

#include <iostream>
#include <stdlib.h>
#include <algorithm>

#define MAX_SIZE 5
using namespace std;
bool isOdd( int integer )
{

    if ( integer % 2 == 0 )
        return false;
    else
        return true;
}


int main()
{
    int median;
    int *minArray ;
    int *maxArray ;
    int myArray[MAX_SIZE];

    for(int i=0; i<20; i++)
    {
        int v = rand() %100;
        cout << v << endl;

        myArray[i%MAX_SIZE] = v;
            if(i==0)
            {
                median = v;
            }

            else if (v>median)
            {
                maxArray= new int [MAX_SIZE+1];
                int n;
                for(n=0; n<(MAX_SIZE+1); n++)
                {
                    if ((median<myArray[n])&&(myArray[n]<=v))
                    {
                        maxArray[n] = myArray[n];
                        //cout<<"asda"<<maxArray[n]<<endl;
                    }
                    else
                    {
                        maxArray[n] = 200;
                        //cout<<"asda"<<maxArray[n]<<endl;
                    }

                }
                if(isOdd(i)&&(i<MAX_SIZE))
                    median = (median+(*min_element(maxArray,maxArray+MAX_SIZE+1)))/2;
                else median = (*min_element(maxArray,maxArray+MAX_SIZE+1));
                //cout << ((*min_element(maxArray,maxArray+MAX_SIZE+1))) << endl;
                delete [] maxArray;
            }
            else if (v<median)
            {
                minArray= new int [MAX_SIZE+1];
                int n;
                for(n=0; n<(MAX_SIZE+1); n++)
                {
                    if ((median>myArray[n])&&(myArray[n]>=v))
                    {
                        minArray[n] = myArray[n];
                        //cout<<"asda"<<minArray[n]<<endl;
                    }
                    else
                    {
                        minArray[n] = 0;
                        //cout<<"asda"<<minArray[n]<<endl;
                    }
                }

                if(isOdd(i)&&(i<MAX_SIZE))
                    median = (median+(*max_element(minArray,minArray+MAX_SIZE+1)))/2;
                else median = (*max_element(minArray,minArray+MAX_SIZE+1));

                delete [] minArray;

            }

            cout << "median: "<< median<<endl;
        }
    return 0;
}

如果我在解释我的问题时犯了一些错误，请原谅，因为我在这里太陌生了。

Answer 1

我认为可能还有其他方法。

由于您现在是数据集的边界，如以下所示:int v = rand() %100; 您还可以跟踪每个数字的出现次数。

您需要将出现次数存储在长度为 100 的数组中。您还需要跟踪“消失”的次数以减少出现次数。

如果你有它，只需从 0 循环...如果你的出现次数大于 MAX_SIZE/2 你那里的 100。

这将是一个 0(n) 操作，但开销很大，尤其是因为数字 0...100 的范围比 MAX_SIZE 5 的范围大得多(反过来会更好)。

无论如何；我认为如果您应用此原则，您的更改数组也不会有问题。

如果您愿意，我可以为您提供一个简单的示例。

编辑

此示例运行不完美，但您可以试一试:

#include <iostream>
#include <stdlib.h>
#include <algorithm>

#define MAX_ELEMENTS 5

#define MAX_VALUE 100

using namespace std;
bool isOdd( int integer )
{

    if ( integer % 2 == 0 )
        return false;
    else
        return true;
}


int main()
{
int median;

int numberOfElements = 0;
int myValueArray[MAX_VALUE];
int myArray[MAX_ELEMENTS];

 //quick n dirty init
 for (int c = 0; c < MAX_VALUE; c++)
    myValueArray[c] = 0;

 for (int c = 0; c < MAX_ELEMENTS; c++)
     myArray[c] = 0;

for(int i=0; i<20; i++)
{
    //generate random number 0...100
    int v = rand() % MAX_VALUE;
    cout << "| " << v << " | "; //incomming value

    myValueArray[v]++;

    int leavingValue = myArray[i%MAX_ELEMENTS]; 
    myArray[i%MAX_ELEMENTS] = v; // just to keep track of leaving value

    if (numberOfElements < MAX_ELEMENTS)
        numberOfElements++;

    else //remove leaving value
    {
        myValueArray[leavingValue]--;
        cout << "| " << leavingValue << " | "; //leaving value
    }

    for (int c = 0, occurances = 0; c < MAX_VALUE; c++)
    {
        occurances += myValueArray[c];

        //(numberOfElements + 1) = dirty indexer correction, but you'll get the point
        if (occurances >= (numberOfElements + 1) / 2)
        {
            if (isOdd(numberOfElements))
                median = c;

            else
                cout << "work to do here...";

            break;
        }
    }

    cout << "array: ";
    //just print the array, to confirm
    for (int c = 0, occurances = 0; c < MAX_VALUE; c++)
    {
        if (myValueArray[c] > 0)
        {
            for (int x = 0; x < myValueArray[c]; x++)
                cout << " {" << c << "}, ";
        }
    }

        cout << " >> median: "<< median<<endl;
    }
   return 0;
}