寻找第K大

题目描述

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

思路解释

• 代码：

  class Finder {
  public:
    int findKth(vector<int> a, int n, int K) {
        int res = 0, left = 0, right = n - 1;
        K = n - K;
        while(left <= right)
        {
            int i = QuickSort(a, left, right);
            if(i == K)
                return  a[i];
            else if(i < K)
                left = i + 1;
            else
                right = i - 1;
        }
        return 0;
    }
  
    int QuickSort(vector<int>& a, int low, int high)
    {
        if(low == high)
            return low;
        int i = low, j = high, key = a[low];
        while(low < high)
        {
            while(low < high && a[high] >= key)
                high--;
            a[low] = a[high];
            while(low < high && a[low] <= key)
                low++;
            a[high] = a[low];
        }
        a[low] = key;
        return low;
    }
  };