( 数组中找第 K 大元素 )
----
文章目录
算法 系列博客
一、快速选择算法
一、快速选择算法
----
数组中找第 K 大元素 : https://www.lintcode.com/problem.../5/
可以 先进行 快速排序 , 然后找第 k 大的元素 ;
先排序 , 在获取值 , 会消耗 排序的时间复杂度
O(n \log n)
;
使用 快速选择算法 , 可以达到
O(n)
的时间复杂度...;
快速选择算法 利用了快速排序算法的步骤 , 快速排序的第一个步骤是从数组中 挑选一个元素 p , 依据 p 将数组分为两部分 , 左侧是小于等于 p 的部分 , 右侧是大于等于 p 的部分 ;...= O(n) + O(\cfrac{n}{2}) + T(\cfrac{n}{4})
时间复杂度计算时 , 只考虑最高次项 , 忽略常数 , 忽略系数 ,
最终的时间复杂度是
O(n)
;
因此使用快速选择算法..., 找数组中的第 K 大元素 , 时间复杂度是
O(n)
;
代码示例 :
class Solution {
/**
* 快速选择算法
* 第 K 大元素