运行中值的恒定大小数组 [英] running median of constant size array
问题描述
我试图找到恒定大小数组的中位数。但是数组总是上升。我的意思是新的数字被旧的数字取代。我调用这个进程运行中位数，或者我们可以说在飞行中值..这里是我的代码和里面的代码，当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（整数％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]）& = v））
{
maxArray [n] = myArray [n];
// cout<<asda<<< maxArray [n]<< endl;
}
else
{
maxArray [n] = 200;
// cout<<asda<<< maxArray [n]<< endl;
}
}
if（isOdd（i）&&（i
else median =（* min_element（maxArray，maxArray + MAX_SIZE + 1））;
// cout<< （（* min_element（maxArray，maxArray + MAX_SIZE +1））））< endl;
delete [] maxArray;
}
else if（v
minArray = new int [MAX_SIZE + 1];
int n;
for（n = 0; n <（MAX_SIZE + 1）; n ++）
{
if（（median> 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
else median =（* max_element（minArray，minArray + MAX_SIZE + 1））;
delete [] minArray;
}
cout<< median：<<中位数
return 0;
}
如果我在解释我的问题时犯了一些错误，请原谅我新来的。
我认为可能有另外一种方法。
您现在是数据集的边界，如下所示： int v = rand（）％100; 您还可以跟踪每个数字的出现次数。 / p>
您需要将数字存储在长度为100的数组中。您还需要跟踪要退出的数字以减少该数字
如果你有那个地方，只要循环从0 ... 100，如果你的发生次数大于MAX_SIZE / 2你的地方。
这将是一个0（n）操作，但是显着的开销，特别是因为数字0 ... 100具有比MAX_SIZE为5更大的范围（反之亦然更好）。
无论如何;我想如果你应用这个原则，你也不会有一个问题，你改变数组。
如果你想我可以提供一个快速的例子。
编辑
此示例无法正常工作，但您可以试试： p>
#include< iostream>
#include< stdlib.h>
#include< algorithm>
#define MAX_ELEMENTS 5
#define MAX_VALUE 100
使用命名空间std;
bool isOdd（int integer）
{
if（整数％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
for（int c = 0; c
for（int i = 0; i <20; i ++）
{
//生成随机数0 ... 100
int v = rand ％MAX_VALUE;
cout<< |<< v<< |; // incomingming value
myValueArray [v] ++;
int leavingValue = myArray [i％MAX_ELEMENTS];
myArray [i％MAX_ELEMENTS] = v; //只是为了跟踪离开值
if（numberOfElements< MAX_ELEMENTS）
numberOfElements ++;
else //删除离开值
{
myValueArray [leavingValue] - ;
cout<< |<< leavingValue<< |; // leave value
}
for（int c = 0，occurances = 0; c
occurances + = myValueArray [c ];
//（numberOfElements + 1）=脏索引器更正，但你会得到点
if（occurances> =（numberOfElements + 1）/ 2）
{
if（isOdd（numberOfElements））
median = c;
else
cout<< 工作在这里做...;
break;
}
}
cout<< array：;
//只打印数组，确认
为（int c = 0，occurances = 0; c
if（myValueArray [c] > 0）
{
for（int x = 0; x
}
}
cout<< >>>>中值：<中位数
return 0;
}
I am trying to find median of constant size array. But array is always uptading. I mean new numbers are replaced with old numbers. I call this process running median, or we can say on the fly median.. Here is my code and inside the code, when rand() function generates 78, the code cannot find the correct median. (Before 78; 41, 67, 34, 0, 69, 24 was generated)
#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;
}
If I made some mistakes about explaning my problem, excuse me cus I am so new here.
I think there might be an alternative way.
Since you now the boundaries of your data set, as denoted by: int v = rand() %100; you can also keep track of the number of occurrences of each number.
You will need to store the number of occurrences in an array which length 100. You'll also need to keep track of the number that's going 'out' to decrease that number of occurrences.
If you have that in place, just loop from 0... 100 if your occurrence count is bigger then MAX_SIZE/2 your there.
This would be a 0(n) operation but with significant overhead, especially because the numbers 0...100 has a much bigger range than the MAX_SIZE of 5 (the other way round would be better).
Anyhow; I think if you apply this principle you also wont have a problem with your changing array.
If you want I can provide you with a quick example.
EDIT
This sample is not working perfectly, but you can give it a try:
#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;
}
这篇关于运行中值的恒定大小数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
