2

一定サイズの配列の中央値を見つけようとしています。しかし、配列は常に更新されています。つまり、新しい番号は古い番号に置き換えられます。私はこのプロセスを実行中の中央値と呼んでいます。または、オンザフライの中央値と言うことができます。これが私のコードで、コード内では、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;
}

問題の説明に誤りがあった場合は、すみません。

4

1 に答える 1

1

別の方法があるかもしれないと思います。

で示されるように、データセットの境界ができたのでint v = rand() %100;、各数値の出現回数を追跡することもできます。

長さ 100 の配列に発生回数を格納する必要があります。また、その発生回数を減らすために、「アウト」する回数を追跡する必要があります。

それが整っている場合は、発生回数が MAX_SIZE/2 よりも大きい場合は、0 から 100 までループします。

これは 0(n) 操作になりますが、特に数値 0 ～ 100 の範囲が 5 の MAX_SIZE よりもはるかに大きいため (逆の方が良いでしょう)、かなりのオーバーヘッドが発生します。

とにかく; この原則を適用すれば、配列の変更にも問題はないと思います。

必要に応じて、簡単な例を提供できます。

編集

このサンプルは完全には機能していませんが、試してみることはできます。

#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;
}
于 2013-10-16T18:15:39.160 に答える