10107 - What is the Median?

[Salman]

Got AC using insertion sort.

[gootsa]

I got several compile error for code below , plz help me

Code: Select all

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
using namespace std;

main()
{
	priority_queue< int , vector<int> , greater<int> > minq;
	priority_queue< int , vector<int> , less<int> > maxq;
	int n;
	while(cin>>n)
	{
		if(minq.size()==0 && maxq.size()==0)
			minq.push(n);
		else if(minq.size()==1 && maxq.size()==0)
		{
			if(minq.top()<n)
				swap(n,minq.top());
			maxq.push(n);
		}
		else
		{
			if(n>minq.top())
				minq.push(n);
			else if(n<maxq.top())
				maxq.push(n);
			else if(minq.size()>maxq.size())
				maxq.push(n);
			else
				minq.push(n);
			if(minq.size()>maxq.size()+1)
			{
				maxq.push(minq.top());
				minq.pop();
			}
			if(maxq.size()>minq.size()+1)
			{
				minq.push(maxq.top());
				maxq.pop();
			}
		}
		if(minq.size()<maxq.size())
			cout<<maxq.top()<<endl;
		else if(maxq.size()<minq.size())
			cout<<minq.top()<<endl;
		else
			cout<<(minq.top()+maxq.top())/2<<endl;
	}
}

[gootsa]

I got several compile error for this code, please help me

Code: Select all

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
using namespace std;

main()
{
	priority_queue< int , vector<int> , greater<int> > minq;
	priority_queue< int , vector<int> , less<int> > maxq;
	int n;
	while(cin>>n)
	{
		if(minq.size()==0 && maxq.size()==0)
			minq.push(n);
		else if(minq.size()==1 && maxq.size()==0)
		{
			if(minq.top()<n)
				swap(n,minq.top());
			maxq.push(n);
		}
		else
		{
			if(n>minq.top())
				minq.push(n);
			else if(n<maxq.top())
				maxq.push(n);
			else if(minq.size()>maxq.size())
				maxq.push(n);
			else
				minq.push(n);
			if(minq.size()>maxq.size()+1)
			{
				maxq.push(minq.top());
				minq.pop();
			}
			if(maxq.size()>minq.size()+1)
			{
				minq.push(maxq.top());
				maxq.pop();
			}
		}
		if(minq.size()<maxq.size())
			cout<<maxq.top()<<endl;
		else if(maxq.size()<minq.size())
			cout<<minq.top()<<endl;
		else
			cout<<(minq.top()+maxq.top())/2<<endl;
	}
}

[mamun]

Code: Select all

error: no matching function for call to `swap(int&, const int&)'

[gootsa]

thank you,
you solve my problem,

I taught that top element of a queue is'nt const, as in visual c++ 6 it compiled whith out error.

[shamim]

1614469.cpp:10: warning: ISO C++ forbids
declaration of `main' with no type
1614469.cpp: In function `int main()':
1614469.cpp:21: conversion from `int' to
non-scalar type `std::_Bit_reference' requested

Here is the compile error message.

[fie]

I tried to solve the problem by using two priority queues, but I got WA-ed a few times after modification. Anyone tell me what's wrong with it?

[code]
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

int main (){
priority_queue<int, vector<int>, greater<int> > minh;
priority_queue<int, vector<int>, less<int> > maxh;

long i;
while (cin >>i)
{

if (minh.size() ==0 && maxh.size() ==0)
minh.push(i);
else
{
if (i >minh.top())
{
if (minh.size() >maxh.size())
{
maxh.push(minh.top());
minh.pop();
}
minh.push(i);
}
else if (i <maxh.top())
{
if (maxh.size() >minh.size())
{
minh.push(maxh.top());
maxh.pop();
}
maxh.push(i);
}
}
if (minh.size() < maxh.size())
cout<< maxh.top() << endl;
else if (maxh.size() <minh.size())
cout <<minh.top() << endl;
else if (minh.top() != 0 && maxh.top() !=0)
cout <<(minh.top() + maxh.top())/2<< endl;
else cout << '0' << endl;

}
return 0;
}
[/code]

[kolpobilashi]

[code]#include<stdio.h>

int main()
{
unsigned long n;
int num=1,arr[1005];
while(scanf("%lu",&n)!=EOF)
{
int a=0,k,ptr;
unsigned long med=0,temp=0;
arr[num]=n;

for(k=1;k<=num;k++)
{
for(ptr=1;ptr<=num-k;ptr++)
{
if(arr[ptr]>arr[ptr+1])
{

temp=arr[ptr];
arr[ptr]=arr[ptr+1];
arr[ptr+1]=temp;
}

}
}

if(num%2==0)
{
a=num/2;
med=(arr[a]+arr[a+1])/2;
}
else
{
a=(num+1)/2;
med=arr[a];
}
num++;
printf("%lu\n",med);
}
return 0;
}

[/b]plz some1 tell me the reason??thanx in advance [/code]

[Jan]

There can be at most 10,000 numbers. Your array size is just 1,005. So, update your array size.

[kolpobilashi]

i increased the array size......but got TLE!!
wat should i do???

[Jan]

There can be at most 10000 numbers. And you are using bubble sort in every step. So, your complexity should be O(n ^ 2). And 10000 ^ 2 complexity should get tle.

I made a sorted linked list. And then found the median. You can also use BST or Heap to solve the problem.

Suppose you have 1 -> 7-> 19. Then you get 16. Traverse the list and enter the new number. So, the list should be...
1 -> 7 -> 16 ->19.

If you get 3 the list should be...
1 -> 3 -> 7 -> 16 -> 19.

This was my idea.

[kolpobilashi]

thanx a lot.

[srabon]

CODE DELETED
I GET ACC

[funningboy]

#include <iostream.h>
#include <string.h>
#include <stdio.h>


const int size=1000;

void msort(int *array,int num); //method
long int process(int *array,int num);

int main(){

int array[size];
int n,i=0;
long int middle;

while(scanf("%d",&n)!=EOF){
array=n;
i++;
msort(array,i);
middle=process(array,i);
cout<<middle;
}

return 0;
}
void msort(int *array,int num){
int temp;

for(int i=0 ; i<num ; i++){

for(int j=i+1 ; j<num ; j++){

if(array[j]<array){

temp=array[j];
array[j]=array;
array=temp;
}
else{
//not do
}
}//for
}
return ;
}


long int process(int *array, int num){

long int middle;
if((num%2)!=0){
//odd
middle=array[(num-1)/2+1];

}else{ //even
middle=(array[(num/2)]+array[(num/2+1)])/2;

}

return middle;
}

[mukeshtiwari]

one thing i did not understand for this problem is when i used heapsort(nlog) then my program is giving TLE when i used insertion sort(n^2) then it accepted and running time was 0.917 when i used shellsort then i got 1.717 and when i used quicksort then i got 4.758 although heapsort and quicksort is consider to best then other sorting algorithm......a sligth modification if u r going for heap sort
chang the code in main like this
i=1;
while(scanf("%d",&a)!=EOF)
{

lengtha=i;
heapsort(a);
if(i%2!=0)
printf("%d\n",a[(i/2)+1]);
else
printf("%d\n",(a[i/2]+a[(i/2)+1])/2);
i++;
}

here is my code in which i added all the sorting algortihm try one by one ....
plz explain me why this is happening ....

#include<stdio.h>


int lengtha,heapsizea;

void maxheapify(int* a,int i)
{

int l,r,largest,t;
l=2*i;
r=2*i+1;
if(l<=heapsizea && a[l]>a)
largest=l;
else
largest=i;
if(r<=heapsizea && a[r]>a[largest])
largest=r;
if(largest!=i)
{
t=a;
a=a[largest];
a[largest]=t;
maxheapify(a,largest);
}
}

void buildmaxheap(int* a)
{
int i;
heapsizea=lengtha;
for(i=lengtha/2;i>=1;i--)
maxheapify(a,i);
}

void heapsort(int* a)
{
int i,t;
buildmaxheap(a);
for(i=lengtha;i>=2;i--)
{
t=a[1];
a[1]=a;
a=t;
heapsizea=heapsizea-1;
maxheapify(a,1);
}
}


void insertionSort(int numbers[], int array_size)
{
int i, j, index;

for (i=1; i < array_size; i++)
{
index = numbers;
j = i;
while ((j > 0) && (numbers[j-1] > index))
{
numbers[j] = numbers[j-1];
j = j - 1;
}
numbers[j] = index;
}
}
void shellSort(int numbers[], int array_size)
{
int i, j, increment, temp;

increment = 3;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers;
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}

void quicksort (int a[], int lo, int hi)
{

int i,j,h,x;
i=lo, j=hi, h;
x=a[(lo+hi)/2];


do
{
while (a<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
h=a; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);


if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
}

main()
{

int aa[10000],i,j;
int* a;
a=aa-1;
i=0;

while(scanf("%d",&aa[i])!=EOF)
{

quicksort(aa,0,i);
//shellSort(aa,i+1);
//insertionSort(aa,i+1);
//lengtha=i;
//heapsort(a);
if((i%2==0))
printf("%d\n",aa[(i/2)]);
else
printf("%d\n",(aa[i/2]+aa[(i/2)+1])/2);

i++;
}
}