寻找第K大数
题目描述
有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。
示例
1 |
|
返回
2
思路
利用快排,每次排序后,将确定位置的数的下标与k-1比较
- 若相等:返回
- 若大于k-1,则在左半部分递归查找
- 如小于k-1,则在右半部分递归查找
代码
1 |
|
寻找第K大数
http://example.com/2020/12/31/寻找第K大数/
有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。
1 |
|
2
利用快排,每次排序后,将确定位置的数的下标与k-1比较
1 |
|