【题解】使用分治法找出第K大的数（递归+分治）

àì夳堔傛蜴生んèń 2023-10-01 20:48 22阅读 0赞

## 题目描述 ##

输入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;
      
    }