215. Kth Largest Element in an Array 第 K 大的数

int findKthLargest(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end(), greater<int>());
    return nums[k-1];
}

int findKthLargest(vector<int>& nums, int k) {
	// 找第K大可以转化成找从小到大排序后 len-k 位置的元素
    k=nums.size()-k;
    int lo=0;
    int hi=nums.size()-1;
    while(lo<hi) {
        int i=partition(nums, lo, hi);
		// 前K个的元素都比主元小，找到
        if (i==k) {
            break;
        } else if (i>k) {
			// 多于 K 个元素比主元小，目标一定在前半边
            hi=i-1;
        } else {
			// 少于 K 个元素比主元小，那么目标一定在后半边
            lo=i+1;
        }
    }
    return nums[k];
}

// 与快排一致的分治排序算法
int partition(vector<int>& nums, int st, int end) {
    int pivot=nums[end];
    int i=st-1;
    for(int j=st;j<end;++j) {
        if (nums[j]<pivot) {
            ++i;
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[end], nums[i+1]);
    return i+1;
}