每日一练之寻找第K大的数

寻找第K大的数

OJ 地址：寻找第K大的数

方法一：快排

class Finder {
public:
    int quickSort(vector<int>& arr, int l, int r, int n, int k) {
        if(l >= r)
            return arr[l];
        int v = arr[l];
        int i = l + 1;
        int j = r;
        while(1)
        {
            while(i <= r && arr[i] < v)
                i++;
            while(j >= l+1 && arr[j] > v)
                j--;
            if(i > j)
                break;
            swap(arr[i++], arr[j--]);
        }
        swap(arr[j], arr[l]);
        if (n - j > k)
            return quickSort(arr, j + 1, r, n, k);
        else if (n - j < k)
            return quickSort(arr, l, j - 1, n, k);
        else {
            return arr[j];
        }
    }
 
    int findKth(vector<int> a, int n, int K) {
        // write code here
       return quickSort(a, 0, n - 1, n, K);
    }
};

方法二：构造一个拥有 K 个元素的最小堆

class Finder {
private:
    
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        priority_queue<int, vector<int> ,greater<int> > pq;
        for(int i = 0; i < n; i++)
        {
            if(pq.size() < K)
            {
                pq.push(a[i]);
            }
            else
            {
                if(a[i] > pq.top())
                {
                    pq.pop();
                    pq.push(a[i]);
                }
            }
        }
      
       return pq.top();
    }
};