题目描述

输入n个数，求其中第k小的数。（要求采用分治法完成，不建议采用完整的排序）

输入要求

第一行包含两个整数n和k；n<1000，1<=K<=n

第二行包含n个整数。

输出要求

输出第k小的那个整数。

输入样例

15 1
1 3 7 2 4 6 -1 0 9 88 2 5 17 6 1

输出样例

-1

解题思路

仿照快排，递归分治的方式，选取数组第一个为基准元素，遍历原数组，构造两个新数组，一个放小于等于基准的所有元素，另一个放大于基准的所有元素。根据条件递归（放代码注释里了）

代码

#include "iostream"
#include "vector"
using namespace std;

//返回vector中第K大的数   k<container.size()
int findKth(vector<int> vec,int k){
  
  vector<int> smallVec;
  vector<int> bigVec;
  int baseEle = vec.at(0);
  for (size_t i = 1; i < vec.size(); i++)
  {
    if(vec.at(i) <= baseEle)     smallVec.push_back(vec.at(i));
    else                         bigVec.push_back(vec.at(i));
  }
  //递归的边界终点 小数组元素数+1==k 表明baseEle为第k大的数 返回该值
  if(smallVec.size()+1 == k)    return baseEle;
  // k小于小数组的个数 说明第k大的数在小数组内部
  if(smallVec.size()  >= k)     return findKth(smallVec,k);
  // k大于小数组的个数 说明第k大的数在大数组内部
  else                          return findKth(bigVec,k-1-smallVec.size());
}

int main (){

  // freopen("input.txt","r",stdin);

  int n,k,temp;
  cin >> n >> k;
  vector<int> inputVec;
  for (int i = 0; i < n; i++)
  {
    scanf("%d",&temp);
    inputVec.push_back(temp);
  }
  cout << findKth(inputVec,k)<<endl;
  
}