第k大数字-ag真人游戏

快排思路实现

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

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

class finder {
  
public:
    int findkth(vector a, int n, int k) {
  
        // write code here
        return findk(a, 0, n-1, k);
    }
    int partition(vector&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& 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 getleastnumbers_solution(vector input, int k) {
  
        for(int i = 0; i < input.size(); i  ){
  
            heapinsert(input, i);
        }
        int headsize = input.size();
        vectorres;
        if(k == 0 || k > headsize) return res;
        if(k == input.size()) return vector(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& 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&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;
        }
    }
};