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

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

admin2014-07-18  74
问题 已知某个序列存在“中值记录”，我们将其定义为：如果将此序列排序后，它是第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://www.kaotiyun.com/show/W4xi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)