问题描述

算法问题：随机时间选择求中位数超出内存限制如何修改

求问：怎么修改才能减少内存占用，还是我写的算法本身不行得重写？

#define MAX 8365000
#include //中位数
#include
#include

long long int randomizedselect(long long int a[],long long int left,long long int right,long long int i);
long long int randomizedpartition(long long int a[],long long int left,long long int right);
long long int partition(long long int a[],long long int left,long long int right);
int swap(long long int,long long int);

long long int a[MAX];
int main()
{
long long int n,m,m1,m2,i;

scanf("%lld",&n);
for (i = 1;i <= n;++i)
{
    scanf("%d",&a[i]);
}

if(n%2 == 1)
    m = randomizedselect(a,1,n,(n+1)/2);
else if(n%2 == 0)
{
    m1 = randomizedselect(a,1,n,n/2);
    m2 = randomizedselect(a,1,n,(n+2)/2);
    m = (m1 + m2)/2;
}

printf("%lld",m);

}

long long int randomizedselect(long long int a[],long long int left,long long int right,long long int i)
{
long long int q,k;
if(left == right)
return a[left];

q = partition(a,left,right);//返回是划分哨兵的最后位置
k = q-left+1;
if(i == k)
    return a[q];
else if (i < k)
        return randomizedselect(a,left,q-1,i);
else
    return randomizedselect(a,q+1,right,i-k);

}

/*long long int randomizedpartition(long long int a[],long long int left,long long int right)
{
long long int i;
srand((unsigned)time(NULL));
i = rand()%(right - left + 1)+left;//产生left和right之间的随机值
swap(right,i);

return partition(a,left,right);

}*/

long long int partition(long long int a[],long long int left,long long int right)
{
long long int x,i,j;
x = a[right];
i = left - 1;
for (j = left;j <= right-1;++j)
{
if(a[j] <= x)
{
i++;
swap(i,j);
}
}
swap(i+1,right);
return i+1;//划分值的位置
}
int swap(long long int x,long long int y)
{
int temp;
temp = a[x];
a[x] = a[y];
a[y] = temp;
}