http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1082. 查找第K小元素
时间限制:1.0s   内存限制:512.0MB  
总提交次数:5537   AC次数:1198   平均分:32.33
将本题分享到:
   
 
问题描述
  给定一个大小为n的数组s和一个整数K,请找出数组中的第K小元素。
  这是一个补充程序的试题,你需要完成一个函数:
  int findKth(int *s, int n, int K)
  表示在s指向的数组中找到第K小的元素(如果K=1,表示找最小元素),你需要返回该元素的值。
  此题对时间的要求比较高,请注意下面的算法描述。
算法描述
  你可以直接将s中的元素进行排序后输出第K小的元素,但使用这种方法你大概只能得到30%的分数。
  要在一个数组中查找第K小的元素,可以模仿快速排序的做法,即对于数组s[0..n-1],首先用数组中的任意一个元素(可以取第一个)将数组分为三个部分:s[0..p-1], s[p], s[p+1..n-1],其中s[0..p-1]中的值都不大于s[p],s[p+1..n-1]中的值不小于s[p]。
  此时,如果p=K-1,则s[p]是要查找的元素,返回s[p]。
  如果p>=K,则第K小的元素一定在s[0..p-1]中,可以在s[0..p-1]中查找第K小的元素。
  如果p<K-1,则第K小的元素一定在s[p+1..n-1]中,而且是s[p+1..n-1]中的第K-p-1小的元素,你可在这一段中查找第K-p-1大的元素即可。注意由于数组可以看作是静态指针,所以s[p+1..n-1]可以看作是以s+p+1指向的数组,你可以在C++中使用s+p+1来表示这个数组。