題目描述：在未排序的數(shù)組中找到第 k 個(gè)最大的元素藕届。請(qǐng)注意亭饵，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素辜羊。
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
方法1：快排后取K大
void quickSort(int *nums, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
int l = startIndex;
int r = endIndex;
int flagNum = nums[startIndex];
while (r > l) {
while (nums[r] > flagNum && r > l) {
r --;
}
while (nums[l] <= flagNum && r > l) {
l ++;
}
if (r > l) {
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
}
nums[startIndex] = nums[l];
nums[l] = flagNum;
quickSort(nums, startIndex, l - 1);
quickSort(nums, r + 1, endIndex);
}
int findKthLargest(int* nums, int numsSize, int k){
quickSort(nums, 0, numsSize - 1);
return nums[numsSize - k];
}
時(shí)間復(fù)雜度為快排的復(fù)雜度：O（N *logN），空間復(fù)雜度O（1）
方法2：對(duì)快排過(guò)程做優(yōu)化八秃，不完全排序
void quickSort(int *nums, int startIndex, int endIndex, int k, int numsSize) {
if (startIndex >= endIndex) {
return;
}
int l = startIndex;
int r = endIndex;
int flagNum = nums[startIndex];
while (r > l) {
while (nums[r] > flagNum && r > l) {
r --;
}
while (nums[l] <= flagNum && r > l) {
l ++;
}
if (r > l) {
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
}
nums[startIndex] = nums[l];
nums[l] = flagNum;
if (l < numsSize - k) {
quickSort(nums, r + 1, endIndex, k, numsSize);
}
else if (l > numsSize - k) {
quickSort(nums, startIndex, l - 1, k, numsSize);
}
else {
return;
}
}
int findKthLargest(int* nums, int numsSize, int k){
quickSort(nums, 0, numsSize - 1, k, numsSize);
return nums[numsSize - k];
}
時(shí)間復(fù)雜度是O（N），空間復(fù)雜度是O（1）
