给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4],k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], 
k = 4
输出: 4

思想：先进行由大到小快速排序。然后输出低k个大的值

代码：

void quickSort(int arr[], int left, int right) {int i = left, j = right;// 选择中间元素作为基准值int pivot = arr[(left + right) / 2];int temp;// 当左指针小于等于右指针时，继续循环while (i <= j) {// 从左向右找到第一个大于或等于基准值的元素while (arr[i] > pivot)i++;// 从右向左找到第一个小于或等于基准值的元素while (arr[j] < pivot)j--;// 如果左指针仍然在右指针的左边，交换这两个元素的位置if (i <= j) {temp = arr[i];arr[i] = arr[j];arr[j] = temp;i++;j--;}};// 递归地对左半部分进行快速排序if (left < j)quickSort(arr, left, j);// 递归地对右半部分进行快速排序if (i < right)quickSort(arr, i, right);
}
int findKthLargest(int* nums, int numsSize, int k) {// 对数组进行快速排序quickSort(nums, 0, numsSize - 1);return nums[k-1]; 
}