2. leetcode 之数组中的第K个最大元素快速排序

青旅半醒 2023-02-21 06:27 12阅读 0赞

**Table of Contents**

1. 题目描述:

2. 解题思路:

3. 知识点总结:

--------------------

## 1. 题目描述: ##

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

示例 1:

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

示例 2:

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

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 2. 解题思路:    ##

最开始比较笨的解题思路, 冒泡排序+数组定位:

int findKthLargest(int* nums, int numsSize, int k){
        int i, j, temp;
    
        for (i = 0; i<k; i++){
            for(j=i+1; j<numsSize; j++){
                if (nums[i] < nums[j]){
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        return nums[k-1];
    }

考虑用快速排序优化后的解题思路及代码:

int compare_data(const void *a, const void *b){
        return *(int *)b - *(int *)a;
    }
    int findKthLargest(int* nums, int numsSize, int k){
        qsort(nums, numsSize, sizeof(int), compare_data);
    
        return nums[k-1];
    }

以上是用快排的库函数实现的, 后续需要自己实现快排算法.

## 3. 知识点总结: ##

reference: [https://www.cnblogs.com/laizhenghong2012/p/8442270.html][https_www.cnblogs.com_laizhenghong2012_p_8442270.html]  
核心: 快速排序 qsort接口函数:  
qsort()  
函数原型

void qsort(  
void \*base,  
size\_t nmemb,  
size\_t size,  
int (\*compar)(const void \*, const void \*)  
);

函数功能：qsort()函数的功能是对数组进行排序，数组有nmemb个元素，每个元素大小为size。

参数base - base指向数组的起始地址，通常该位置传入的是一个数组名  
参数nmemb - nmemb表示该数组的元素个数  
参数size - size表示该数组中每个元素的大小（字节数）  
参数(\*compar)(const void \*, const void \*) - 此为指向比较函数的函数指针，决定了排序的顺序。

比较函数的接口实现, 这个可以背下, 改变a-b的顺序, 可以改变排序的大小顺序.  
int compare\_data(const void \*a, const void \*b)\{  
return \*(int \*)b - \*(int \*)a;  
\}

后续: 研究快排原理, 并用代码实现.

[https_www.cnblogs.com_laizhenghong2012_p_8442270.html]: https://www.cnblogs.com/laizhenghong2012/p/8442270.html