经典题目总结篇

1. 第k大：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int size = nums.size();
        int position = partation(nums, 0, size - 1, size - k + 1);
        return nums[position];
    }
    int partation(vector<int>& nums, int low, int high, int k){
        int pivot = nums[high], i = low, j = high;
        while(i < j) if(nums[i++] > pivot) swap(nums[--i], nums[--j]);
        swap(nums[i], nums[high]);
        
        int m = i - low + 1;
        
        if(m == k) return i;
        else if(m > k) return partation(nums, low, i - 1, k);
        else return partation(nums, i + 1, high, k - m);
    }
};