寻找数组中第K大的元素
已关闭dadingPython / C++入场费 2 金币1 次提交
题目描述
给定一个整数数组和整数 k，找出数组中第 k 大的元素。
注意：第 k 大指的是排好序后从大到小第 k 个元素。例如数组 [3,2,1,5,6,4]，第 2 大的元素是 5。
要求时间复杂度优于 O(n log n)。
输入格式
第一行两个整数 n 和 k（1 ≤ k ≤ n ≤ 10^5），第二行 n 个整数，绝对值不超过 10^9。
输出格式
一个整数，第 k 大的元素。
输入输出样例
样例 1
输入：
6 2 3 2 1 5 6 4
输出：
5
样例 2
输入：
5 1 2 1 5 3 4
输出：
5
说明/提示
考虑快速选择算法（QuickSelect），平均时间复杂度 O(n)。