描述：同上
错误代码c语言代码⬇️
无
错误原因：无
正确代码c语言代码⬇️
//思路：先排序，然后再找第k大的数
void quicksort(int* ary, int low, int high){
int l = low;
int r = high;
if(l >= r)
return ;
int pivot = l;
int key = ary[pivot];
while(l < r){
while(l < r && ary[r] <= key)
r--;
ary[pivot] = ary[r];
pivot = r;
while(l < r && ary[l] >= key)
l++;
ary[pivot] = ary[l];
pivot = l;
}
ary[pivot] = key;
quicksort(ary, low, pivot-1);
quicksort(ary, pivot+1, high);
}
int findKthLargest(int* nums, int numsSize, int k){
quicksort(nums, 0, numsSize-1);
return nums[k-1];
}
填坑法快排，彳亍
执行结果：
通过
显示详情
执行用时：80 ms
, 在所有 C 提交中击败了22.32%的用户
内存消耗：6.2 MB
, 在所有 C 提交中击败了54.79%的用户
通过测试用例：
32 / 32
快排时间复杂度nlog(n)在c语言中击败20%左右的用户，看来此方法仍然有点慢，应该有更好的方法。
思考樂
思考结果2:用一个大小为k的数组来存放当前遍历的最大的k个值，每遍历一个值就和新建的数组从尾到头比较并进行替换判断，似乎时间复杂度可以达到0（n2）,应该是不如快排。
思考结果3：申请大片存储空间，用数组存储每个数字出现的次数，再从尾到头统计次数，到达k时输出下标，用空间换时间，时间复杂度o(n)，空间复杂度也会达到o(n)。
思之无果，上网搜之，应用堆排序。
代码如下⬇️
堆排序思路：
1.将数组视为一个堆
2.进行建堆操作，从第一个非叶节点（length/2）开始往上遍历，不断的调整至符合堆的性质
3.开始堆排序，将堆顶元素与最后元素进行交换，将交换后的堆看成两个堆，1⃣️由原堆顶元素组成的有序堆，2⃣️由最后元素交换过去后的待调整的无序堆。现在对堆顶元素进行调整，调整好后继续进行步骤3.
最后可形成有序堆
//思路：先排序，然后再找第k大的数，此处是建立大顶堆，排序后由小到大
void adjustHeap(int *arr, int i, int length){
int temp = arr[i];
for(int k = i*2+1; k < length; k = k*2+1){
if(k+1 < length && arr[k+1] > arr[k] ){
k++;
}
if(arr[k] > temp){
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;
}
void heapSort(int* arr, int length){
for(int i = length/2 - 1; i >= 0; i--){
adjustHeap(arr, i, length);
}
for(int i = length - 1; i > 0; i--){
swap(&arr[i], &arr[0]);
adjustHeap(arr, 0, i);
}
}
void swap(int* a,int* b){
int t = *a;
*a = *b;
*b = t;
}
int findKthLargest(int* nums, int numsSize, int k){
heapSort(nums, numsSize);
return nums[numsSize - k];
}
执行结果：通过
显示详情
执行用时：8 ms, 在所有 C 提交中击败了82.05%的用户
内存消耗：6.1 MB, 在所有 C 提交中击败了58.47%的用户
相比于前者提高明显
趁热打铁，通过建立小顶堆，获得一个递减的序列
//趁热打铁，写一个小顶堆来联系
void adjustHeap(int* arr, int i, int length){
int temp = arr[i];
for(int k = i*2+1; k < length; k = k*2+1){
if(k+1 < length && arr[k+1] < arr[k]){
k++;
}
if(arr[k] < temp){
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//此处极易忘记，应该给调整的元素一个安家之所
//！！！！！应加倍小心
}
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void heapSort(int* arr, int length){
for(int i = length/2-1; i >= 0; i--){
adjustHeap(arr, i, length);
}
for(int i = length-1; i > 0; i--){
swap(&arr[0], &arr[i]);
adjustHeap(arr, 0, i);
}
}
int findKthLargest(int* nums, int numsSize, int k){
heapSort(nums, numsSize);
return nums[k-1];
}
第二天练习堆排序，代码如下⬇️
// 再来一遍堆排序,建立大顶堆，递增序列
void adjustHeap(int* arr, int i, int length){
int pivot = arr[i];
for(int k = i*2+1; k < length; k = k*2+1){
if(k+1 < length && arr[k+1] > arr[k]){
k++;
}
if(arr[k] > pivot){
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = pivot;
}
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void heapSort(int* arr, int length){
for(int i = length/2-1; i >= 0; i--){
adjustHeap(arr, i, length);
}
for(int i = length-1; i > 0; i--){
swap(&arr[i], &arr[0]);
adjustHeap(arr, 0, i);
}
}
int findKthLargest(int* nums, int numsSize, int k){
heapSort(nums, numsSize);
return nums[numsSize-k];
}
容易出错的地方：再heapSort的第二个for循环里的adjustHeap方法中的第三个参数，随着每一次堆顶和堆尾的交换，原有堆的长度在不断的减小，所以应该是i，而不应该是length。
原参考的代码中，在adjustHeap函数中，被比较的元素命名为temp，私以为命名为pivot更加合适，被调整的元素更像快排中的pivot元素，一直用做和其他元素进行比较，命名为pivot更加见名知义。
总结总结：桥洞底下盖小被，啊堆堆堆
