第k大数字-快排，大根堆实现

快排思路实现

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

class finder {
  
public:
    int findKth(vector<int> a, int n, int K) {
  
        // write code here
        return findK(a, 0, n-1, K);
    }
    int partition(vector<int>&arr, int left, int right){
  
        int pivot = arr[left];
        while(left < right){
  
            while(left < right && arr[right] <= pivot){
  
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] >= pivot){
  
                left++;
            }
            arr[right] =  arr[left];
        }
        arr[left] = pivot;
        return left;
    }
    int findK(vector<int>& a, int left, int right, int k){
  
        if(left <= right){
  
            int pivot = partition(a, left, right);
            if(pivot == k-1) return a[pivot];
            else if(pivot < k-1){
  
                return findK(a, pivot+1, right, k);
            }else if(pivot > k-1){
  
                return findK(a, left, pivot-1, k);
            }
           
        }
         return -1;
    }
};

堆排

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

class Solution {
  
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
  
        for(int i = 0; i < input.size(); i++){
  
            heapInsert(input, i);
        }
        int headSize = input.size();
        vector<int>res;
        if(k == 0 || k > headSize) return res;
        if(k == input.size()) return vector<int>(input.begin(), input.end());
        
        res.push_back(input[0]);
        swap(input[0],input[--headSize]);
        
        while(--k ){
  
            heapify(input, 0, headSize);
            res.push_back(input[0]);
            swap(input[0],input[--headSize]);
        }
        return res;
    }
    void heapInsert(vector<int>& a, int index){
  
        while(index > 0 && a[index] < a[(index-1)/2]){
  
            swap(a[index], a[(index-1)/2]);
            index = (index - 1) / 2;
        }
    }
    void heapify(vector<int>&arr, int index, int size){
  
        int left = index * 2 + 1;
        while(left < size){
  
            int smallest = ((left + 1 < size) &&(arr[left+1] < arr[left])) ? left+1:left;
            smallest = arr[smallest] < arr[index] ? smallest : index;
            if(smallest == index)break;
            swap(arr[smallest], arr[index]);
            index = smallest;
            left = index * 2 + 1;
        }
    }
};