2 aptenodytesfosteri aptenodytesfosteri 于 2016.04.03 22:17 提问

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

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

#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;
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
【算法导论】中位数和顺序统计量之选择算法
本文阐述了如何使用期望和线性时间的选择算法求得第i顺序统计量,欢迎拍砖!
线性时间查找中位数算法
一般来说,中位数的查找算法都是基于先排序,后找中间位置的数字的算法,但是因为线性时间排序所收到的限制比较大,而如果使用基于比较的排序,时间复杂度将至少为O(nlogn),如何以线性时间完成中位数或者数组中第N大元素的查找呢?
线性时间选择中位数算法
线性时间选择,中位数算法,利用按每5个元素分组,分别找出其中位数,再递归找出
[C/C++] 用线性时间选择来找无序数组的中位数
有一道题大概是这样的:有n条水平的线,知道线的纵坐标,选择一条线,使得这条线到所有线的距离之和最小。根据数学知识,我们知道,如果线是奇数条的话,那么中间那条(纵坐标的中位数)即可,如果是偶数条的话,那么中间那2条区间内的都可以,而如果要线的纵坐标尽可能小,那么就取中间两条纵坐标较小的那条即可。那么在线数量为偶数的时候,这并不是传统的求中位数问题,而线数量为奇数的时候,则变成传统的中位数问题。求中位...
线性时间的中位数查找算法
原帖链接 一、以期望线性时间做选择 一般来说,中位数的查找算法都是基于先排序,后找中间位置的数字的算法,但是因为线性时间排序所收到的限制比较大,而如果使用基于比较的排序,时间复杂度将至少为O(nlogn),如何以线性时间完成中位数或者数组中第N大元素的查找呢? 快速排序算法在每一次局部递归后都保证某个元素左侧的元素都比他小,右侧的元素都比她大,因此,可以利用这个思路快速找
算法实验之分治法求中位数
利用分治策略试设计一个O (log n)时间的算法求出这2n个数的中位数。 要输入的内容在文件1.txt中,输出的结果在文件2.txt中。 #include #include using namespace std; template T mid(T *a,T *b,int len) { if(len==1) return *a<*b?*a:*b; if(len==2) { i
主元素,中位数以及快速排序问题(分治法问题)
IBM最后有道求主元素的题目,一个数组有N个元素,其中有超过N/2的元素相同,请找出这个元素。时间复杂度为O(n) 方法1:如果一个元素的个数超过N/2则这个元素必然是这N个元素的中位数。则这个题目是找中位数。方法是通过快速排序变化的来的算法。 代码如下:#include #i
顺序统计量和中位数——线性时间的选择算法
一、求最大最小值 即遍历一次,然后依次跟当前最大或最小的比较一下,遍历结束,则选择结束。 (源代码来自网上) //得到最小值 int GetMin(int nData[], int nLen) { int nMin = nData[0]; //初始化nMin为第一个数据 for (int i = 1; i < nLen; ++i) //遍历数据一一同nMi
求中位数,快速选择算法
实验五    输油管道问题的设计与实现 [实验目的] 1、掌握分治算法的基本原理 2、利用分治策略编程解决输油管道问题 [实验内容] 问题描述 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置
编程中内存限制问题
1、ACM内存限制经常写32768kb,其实就是32M(准确值,没有误差),以字节为单位(后面不再重复),用16进制表示为:0x 2 00 00 00。关于一般ACM题目所给的内存限制,另一种具体的表述方法就是:800万32位整型数组或400万64位整型数组。         2、事实上,以16进制表示内存非常有意思,1M即为0x 10 00 00。         而1M就是VC或C-Fre