前k大的数

一、前k大的数?

取前 k 个数,并取出最小值(mi(k) = min(k, n)).
遍历 第 k+1 ~ n的数,与 mi(k) 比较。若小于 mi(k),遍历下一个。若大于 mi(k),放入该值,并移除mi(k)后,再次取出最小值(mi(k) = min(k, n))。

时间复杂度:O(N * K)。

二、找第k到m(0<k<=m<n)大的数?

1. 将数据分成三个区间:
(1~k-1, k~m, m+1~n),目标是取出适合于k~m区间的数。

2. 操作 前两个区间,即 1~k-1 和 k~m:
(1) 找出第k-1大的数:从 1~k-1 中,取最大值(方法很多:冒泡,冒一次;直接选择,一趟选最大)。ma(k-1) = max(k-1, n)。时间复杂度 O(k-1).
(2) 利用快速排序,对 1~m 进行一次快排(不需要整体有序),1~k-2 大的数会被分到 k-1 的左边,k~m大的数分到 k-1 的右边。时间复杂度 O(m).
(3) 从 k~m 中,找出最大值和最小值。ma(m) = max(m, m),mi(k) = min(k, m).时间复杂度 O(2(m-k)).

3. 遍历 m+1~n 的数(nx = n(x)),与 第 k-1 大的数进行比较.
小于 k-1的数,即nx < ma(k-1),放入左边;右边收录n(k-1),(比较n(k-1)与ma(m),大的数被淘汰出去。受影响的区域,最值从新获取。时间复杂度 O((n-(m+1))*(k-1)).


时间复杂度(比较复杂):O((n-(m+1))*(k-1)) = (K-1) + m + 2(m-k) + (n-(m+1))*(k-1).

原文地址:https://www.cnblogs.com/bridgestone29-08/p/13100163.html