текущая медиана массива постоянного размера
Я пытаюсь найти медиану массива постоянного размера. Но массив всегда обновляется. Я имею в виду новые номера заменяются старыми номерами. Я называю этот процесс запущенным медианой, или мы можем сказать на лету медианой. Вот мой код и внутри кода, когда функция 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;
}
Если я допустил некоторые ошибки в объяснении своей проблемы, извините меня, потому что я такой новый здесь.
Решение
Я думаю, что может быть альтернативный путь.
Так как вы теперь границы вашего набора данных, как обозначено: int v = rand() %100; Вы также можете отслеживать количество вхождений каждого номера.
Вам нужно будет хранить количество вхождений в массиве, длина которого равна 100. Вам также нужно будет отслеживать количество выходящих, чтобы уменьшить это количество вхождений.
Если у вас это есть, просто зацикливайтесь от 0 … 100, если количество вхождений больше, чем MAX_SIZE / 2 у вас там.
Это будет операция 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;
}
Другие решения
Других решений пока нет …