查找第k个最小数-可变数组(c++版)

#include <iostream>
 
using namespace std;
  
int findK(int arrayNum[], int p, int r, int k) {
    /**
    *在数组arrayNum[p:r]中查找第k（k > 0)个元素（下标为p+k-1)
    * p <= r && 0 < k && k <= p - r +1 （合法输入说明）
    *渐进时间复杂度/平均时间复杂度 O(N)
    */
    int i = p, j = r, key = arrayNum[i];
    while (i < j) {
        while (i < j && arrayNum[j] >= key)
            --j;
        arrayNum[i] = arrayNum[j];
        while (i < j && arrayNum[i] <= key)
            ++i;
        arrayNum[j] = arrayNum[i];
    }//循环结束后 i = j,其实前面这些语句就是快排的一次划分
    arrayNum[i] = key;
    int lefts = i - p + 1;
    if (lefts == k) 
        return arrayNum[i];//找到中位数了
    if (lefts > k) //比关键字小的数的个数大于k，则中位数在左边
        return findK(arrayNum, p, i - 1, k);
    else
        return findK(arrayNum, i + 1, r, k - lefts);
}


int main()
{
     int n;
     int i=0;
    cout<<"请输入要创建的数组的长度"<<endl;
    cin>>n;
    //分配动态一维数组 
    int *arr=new int[n];
   cout<<"请输入要数组的元素"<<endl;
    for(i=0;i<n;i++)
        cin>>arr[i];

    cout<<"您输入的数组为: ";
    for(i=0;i<n;i++)
       cout<<arr[i]<<" ";
    cout<<endl;
  
    cout<<"请输入要查找第几个最小数，数字要小于等于"<<n<<endl;
    int m=0;
    cin>>m;
    int result=0;
    result=findK(arr,0,n,m+1);
    cout<<"结果为"<<result<<endl;

    
    return 0;
}

请输入要创建的数组的长度
4
请输入要数组的元素
1 2 2 3
您输入的数组为: 1 2 2 3
请输入要查找第几个最小数，数字要小于等于4
3
结果为2