algorithm - 快速选择算法找到第 k 个最小的

Question

我正在尝试使用快速选择来查找第 k 个最小的数字。但是当我编写与https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/完全相同的代码时，它会给出错误的输出，但是当我从 GeeksforGeeks 复制代码时它可以工作。我使用相同的头文件，但它不起作用。

我的代码是

   #include <bits/stdc++.h>
using namespace std;
int partition(int arr[],int l,int r);
void swapp(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}



int kthsmallest(int arr[],int l,int r,int k)
{
    if(k > 0 && k <= r - l + 1)
    {
        int pos = partition(arr,l,r);

        if(pos-1 == k-1)
        {
            return arr[pos];
        }
        if(pos-1 > k-1)
        {
            return kthsmallest(arr,l,pos-1,k);
        }

        return kthsmallest(arr,pos+1,r,k-pos+l-1);
    }

    return INT_MAX;
}
int partition(int arr[],int l,int r)
{
    int x = arr[r];
    int i = l;
    for(int j = l;j<=r-1;j++)
    {
        if( arr[j] <= x)
        {
            swapp(&arr[i],&arr[j]);
            i++;
        }
    }
    swapp(&arr[i],&arr[r]);
    return i;
}

int main()
{
    int n;
    cin>>n;

    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }

    int k;
    cin>>k;

    cout<<"kth smallest "<<kthsmallest(arr,0,n-1,k);
    return 0;
}

Answer 1

您在整个代码中混合了“1（一）”和“l（字母 L）”。如果你修复它，它的工作原理