寻找第k大or第k小的数--＞寻找中位数

Love The Way You Lie 2022-11-29 11:27 134阅读 0赞

> 快排思想，选取数组中第一个元素e为参考元素，利用partition() 使得数组左边的元素全都不大于e，数组右边的元素全都不小于e–>升序排序

> 设数组长度为n，若e的下标m恰好为n-k，则寻找到第k大的元素，即e；若e的下标m恰好为k-1，则寻找到第k小的元素，即e

> 如果m>n-k，在e元素的左半边递归寻找；如果m<n-k, 在e元素的右半边递归寻找

> 如果m>k-1，在e元素的左半边递归寻找；如果m<k-1, 在e元素的右半边递归寻找

> 寻找中位数–>k = (n/2) + (n%2)，数组长度为奇数时向上取整，即(n/2) + 1

int Partition(int* arr,int low ,int high)
    {
        
        int temp = arr[low];
        while(low < high)
        {
        
            while(low < high && arr[high] >= temp)
                high--;
            arr[low] = arr[high];
            while(low < high && arr[low] <= temp)
                low++;
            arr[high] = arr[low];
        }
        arr[low] = temp;//确定参考元素的位置
        return low;
    }
    int KthElement(int * arr,int low, int high,int n ,int k)
    {
        
        if(arr == nullptr || low >= high || k > n)//边界条件和特殊输入的处理
            return 0;
        int pos = Partition(arr,low,high);
        while(pos != n  - k)
        {
        
            if(pos > n - k)
            {
        
                high = pos - 1;
                pos = Partition(arr,low,high);
            }
            if(pos < n - k)
            {
        
                low = pos + 1;
                pos = Partition(arr,low,high);
            }
        }
        return arr[pos];//pos=n-k,递归结束
     
    }
     
    int main()
    {
        
     
       int a[]={
        1,5,5,7,88,11};
       cout<<KthElement(a,0,5,6,2);
       
    }