已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。 请回答下列问题: (1)给出算法的主要思想; (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释

admin2014-07-18  41

问题 已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。
  请回答下列问题:
  (1)给出算法的主要思想;
  (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释;
  (3)总结所用算法的时间和空间复杂度。

选项

答案(1)为了获取中值记录,我们将数组中的元素分成两组,一组是比当前记录大的数值,另外 一组是小于当前记录的数值。如果两组记录的数据数目相等或是最为接近,那么当前记录 即为要找的中值记录。 (2)算法的实现函数: ty pedef struct{ int g;//大于该记录的个数 int t;//小于该记录的个数 }place; im Get—Mid(int a[],int n){//获取中值记录的函数 place b[MAXSIZE]; /*对第i个元素统计比它大和比它小的元数的个数,分别为g和t*/ for(int i=0;ia[i])b[i].g++; if(a[j]2),算法实现过程中使用的辅助空间为数组,空间复杂度为O(n)。

解析
转载请注明原文地址:https://kaotiyun.com/show/W4xi777K
0

最新回复(0)