第k小元素（顺序统计量）

在一个含有n个元素的集合中，有时我们需要找到第该集合中第 k 个小的元素，这也被称作第k个顺序统计量(order statistic)。在前面我们已学过排序, 我们可以将集合进行排序后，直接输出第 k 个元素。但是我们目前我们知道的排序中最好的时间复杂度就是O(nlog(n)). 接下来我们要使用两种方法找出第k小元素，其在某些过程用到排序，但我们并不会对整个集合进行排序，也不会使得最终的集合是顺序的。这两中方法一个是期望时间复杂度是 O(n) , 而另一个实际时间复杂度就是 O(n) .

1. 期望时间的选择算法

算法思想

这里我们要用到快速排序的思想，快速排序是将 1 个关键字pivot_key排到整个集合中的正确位置，并将整个集合分成两个部分，左边都不比它大，而右边的都不比它小，如果我们现在将这个关键字pivot_key所在位置pivot_pos和我们的k（所要求的第 k 个顺序统计量）比较，若相等则返回；若小于则访问pivot_key左边的第k个顺序统计量；否则访问pivot_key右边的第 k−pivot_pos 个顺序统计量（不包括pivot_key）。

算法实现

下面我们直接通过代码来说明问题：

int randomized_Partition(int *arr, int from, int to) {
int pivot_key = arr[from];
int low = from;
int high = to;
while (low < high) {
while (low < high && pivot_key <= arr[high]) {
--high;
}
arr[low] = arr[high];
while (low < high && pivot_key >= arr[low]) {
++low;
}
arr[high] = arr[low];
}
arr[high] = pivot_key;
return high;
}

上面的代码我们很容易就是快速排序将集合分成两部分，并放回pivot_key, 正确的位置。

int randomized_select(int *arr, int from , int to, int i) {
if (from == to) {
return arr[from];
}
// 算出arr[from] 所在的 pivot 位置
int q = randomized_Partition(arr, from, to);
// arr[from] 所在序列中第几个元素
int k = q -from + 1;
int result;
if (i == k) {
result = arr[q];
} else if (i < k) {
result = randomized_select(arr, from, q - 1, i);
} else {
result = randomized_select(arr, q + 1, to, i - k);
}
return result;
}

这剩下的这一部分代码就是我们上述提到的核心思想。

算法分析

z这里我们主要分析它为什么期望时间是 O(n) , 我们在这里假设 Xk 表示有k个元素的事件，且经过一次randomized_Partition我们要找的第 i 个顺序统计量都在Xk(即pivot_key的左边部分或右边部分)里，且 P(Xk=1)=1n ( Xk 这事件会发生的概率), 这样我们从上面的randomized_select可以分析到其时间复杂度 T() 满足如下关系：

2. 最坏情况为线性时间的选择算法

算法步骤

先假设我们这个算法函数为Select()
1) 将输入数组arr的 n 个元素划分为⌊15⌋, 每组 5 个元素，且之多只有一组剩下的nmod5个元素组成。
2) 找这 ⌈n5⌉ 组中每一组的中位数：首先对每组元素进行插入排序，然后确定每组有序元素的中位数。
3) 对第2步中找出的 ⌈n5⌉ 个中位数，递归调用Select()找出其中位数 x
4) 利用修改过的partition函数，找出这个x在整个数组arr中, 的正确位置 i ，这样就使得在数组arr中，左边的数都不比它大，而右边的数都不比它小。
5) 如果i=k, 则返回x。因此x就是第 k 小元素。如果i<k, 则在 x 的左边找第i小的元素。否则在 x 的右边（不包括x）找第 i−k 小的元素。
t通过 上述算法描述，我们可以利用下面一张图进行形象化。

算法实现

插入排序

// 插入排序
void insertSorting(int *arr, int from, int to) {
int i, j, t;
int sc;
for (i = from + 1; i <= to; ++i) {
sc = arr[i];
j = i - 1;
while(j >= from) {
// 找到一个不满足arr[j] <= sc
if (arr[j] > sc) {
--j;
} else {
break;
}
}
// 将arr[j + 1, i - 1]向前移动一个位置
// 即arr[j + 2, i]
for (t = i; t > j; --t) {
arr[t] = arr[t - 1];
}
arr[j + 1] = sc;
}
}

改版的partition

// 讲指定位置pivot的元素作为主元
int partition(int *arr, int from, int to, int pivot) {
int sc = arr[pivot];
swap(arr + from, arr + pivot);
int low = from;
int high = to;
while (low < high) {
while (low < high && sc <= arr[high]) {
--high;
}
arr[low] = arr[high];
while (low < high && sc >= arr[low]) {
++low;
}
arr[high] = arr[low];
}
arr[low] = sc;
return high;
}

上述算法核心就是BFPRT算法：

// 利用BFPRT 求解第k小元素
int BFPRT(int *arr, int from, int to, int ith) {
// 当元素小于5个的时候直接插入并且返回
if(to - from + 1 <= 5) {
insertSorting(arr, from, to);
return arr[from + ith - 1];
}
int t = from - 1;
// 作为每5个数组的开始和结束的index
int st, ed;
// 至少有一组元素能进入这个循环, 也就是 to - from + 1 > 5
for (st = from; (ed = st + 4) <= to; st += 5) {
insertSorting(arr, st, ed);
++t;
swap(arr + t, arr + st + 2);
}
// 关心的是中位数的位置，而不是中位数的值
int pivot = (from + t) >> 1;
BFPRT(arr, from, t, pivot - from + 1);
int m = partition(arr, from, to, pivot);
// pivot 为第几小
int cur = m - from + 1;
int res;
if (cur == ith) {
res = arr[m];
} else if (cur < ith) {
res = BFPRT(arr, m + 1, to, ith - cur);
} else {
res = BFPRT(arr, from, m - 1, ith);
}
return res;
}

算法分析

从上图分析，如果我们去掉数组arr最右边不足5个那一组，以及中位数 x 所在的那一组，我们可以判定x至少大于这么多数

步骤

耗时

对⌈n/5⌉个数组分别进行插入排序 O(n) 对 ⌈n/5⌉ 个中位数查找他们之间的中位数 T(⌈n/5⌉) 最坏情况下，对剩下的元素查找第 k 小元素

T(7n/10+6) f(n)=O(n) 就不详细数学公式证明(读者可以尝试使用 f(n)=an+b 来证明)。 讨论 期望为线性时间的选择算法和最坏情况为线性时间的选择算法有什么区别？ 期望为线性时间的选择算法每次都是选择的 arr[from...to] 中的第 1 个作为pivot_key，所以它下一次查找的子数组的个数是不确定，具有很大的随机性，所以它在概率下时间复杂度为O(n)；而最坏情况为线性时间的选择算法它每次选择的pivot_key是特定的，这个特定的pivot_key使得至少有 3n10−6 个元素比其小或等于，在最坏情况下，我们只需要对剩下的 7n/10+6 个元素组成的子集进行查找我们需要的第 k <script type="math/tex" id="MathJax-Element-62">k</script>小元素。 致谢 本文是基于《算法导论》写的，最主要的是有本人大量的心得体会，感谢《算法导论》的那些作者Thomas H.Cormen、Charles E.Leiserson等 人。如果有错误的请留言，不甚感激。谢谢。 参考 《算法导论》Thomas H.Cormen、Charles E.Leiserson等 第三版 第9章 “中位数和顺序统计量” 源代码： 等上传完，附上 转载，请注明 fourye007 关注 关注 0 点赞 踩 0 收藏 打赏 知道了 0 评论 第k小元素（顺序统计量） 在一个含有n个元素的集合中，有时我们需要找到第该集合中第kk个小的元素，这也被称作第kk个顺序统计量(order statistic)。在前面我们已学过排序, 我们可以将集合进行排序后，直接输出第kk个元素。但是我们目前我们知道的排序中最好的时间复杂度就是O(nlog(n))O(nlog(n)). 接下来我们要使用两种方法找出第k小元素，其在某些过程用到排序，但我们并不会对整个集合进行排序，也不会使 复制链接 扫一扫 专栏目录 第K小元素（分治法） 11-17 给定一个线性序列集，要求求出其中指定的第K小的数的值和位置，如给定n个元素和一个整数i，1≤i≤n，输出这n个元素中第i小元素的值及其位置 第六章 样本与抽样分布 最新发布 qq_64042766的博客 02-20 14 ## 一、计算含有$overline X^2$，$S^2$的统计量的期望和方差 1. 首先，将此统计量转换为$chi^2$分布. 2. 然后利用$chi^2$分布的期望、方差进行计算。 3. 若统计量中含有$overline X^2$，可用定义将其转换为$chi^2$分布；若统计量中含有$S^2$则可用公式$frac{(n-1)S^2}{σ^2}simchi^2(n-1)$将其转换为$chi^2$分布。 参与评论 您还未登录，请先 登录 后发表或查看评论 【算法导论】第六课 顺序统计，中值 Lost in your eyes 03-12 886 这一节课讲到两个线性算法，一个是顺序统计算法（Order Statistics）还有一个是最坏情况线性时间顺序统计法（Worst-case linear-time order statistics） 这两个算法是要解决这样一个问题：对于一个数组A，我们需要求得第k小的一个数，rank（k） 如果k=1， 就是求最小值 如果k=n， 就是求最大值 如果k=[(n+1)/2] or [(n 第K顺序统计量的求解 dbbaq24022的专栏 06-22 476 一个n个元素组成的集合中，第K个顺序统计量（Order Statistic）指的是该集合中第K小的元素，我们要讨论的是如何在线性时间（linear time）里找出一个数组的第K个顺序统计量。 一、问题描述 问题：给定一个含有n个元素的无序数组，找出第k小的元素。 k = 1 ：最小值k = n ：最大值k = ⌊(n+1)/2⌋ or ⌈(n+1)/2⌉ ：中位数 ... 算法基础-顺序统计量 DearXuan的博客 01-30 1367 顺序统计量 将长度为 n 的数组升序排序后，则第 i 个位置的数字是该数组的第 i 小的量，称之为第 i 顺序统计量 数组最小值是第1个顺序统计量，最大值是第n个顺序统计量，中位数(又称下中位数)是第⌊(n+1)/2⌋个顺序统计量 ⌊n⌋ 表示对 n 向下取整，⌈n⌉表示对 n 向上取整 最大值和最小值 若想要寻找n个数字里的最大值或最小值，只需要进行(n-1)次比较 int min = a[0]; for(int i=1;i<n;i++){ if(a[i] > min 顺序统计量 Mr.wei的小站 07-28 9836 从现在开始，一起写代码的同学越来越多，在验证自己程序正确性的同时，还要不断提高自己程序的运行速度，总不希望自己的程序比同学的要慢，快还是好的。今天总结顺序统计量的相关问题，以及程序的优化。 漫步数理统计三十四——顺序统计量 蜗牛 06-22 9560 本篇博文将定义顺序统计量并讨论这种统计量的一些简单性质。近些年来这种统计量在统计推断中占有重要角色，因为他们的某些性质不依赖于得到随意样本的分布。X1,X2,…,XnX_1,X_2,ldots,X_n表示连续型分布中得到的随机样本，其pdf为f(x)f(x)支撑为=(a,b),−∞≤a<b≤∞mathcal{S}=(a,b),-inftyleq a<bleqinfty，Y1Y_1是Xi 求解顺序统计量的7种方法 weixin_51648153的博客 12-02 782 求解顺序统计量的基本知识，求解Max和Min数，求解Min和Sec_Min的数，求解带权值的中位数。 选择问题（求第k个最小元素） 车子（chezi） 05-27 8840 什么是选择问题 划分的思路 Lomuto 划分 利用划分求第k小元素 C语言实现 改进 参考资料 什么是选择问题 选择问题（selection problem）是求一个n个数列表的第k个最小元素的问题。这个数字被称为第k个顺序统计量（order statistic）。当然，对于k=1或者k=n的情况，我们可以扫描整个列表，找出最小或者最大的元素。对于其他情况，我们可以对列表进行排序... 算法打基础——顺序统计(找第k小数) weixin_30727835的博客 10-26 159 这次主要是讲如何在线性时间下找n个元素的未排序序列中第k小的数。当然如果(k=1 or k=n)，即找最大最小 数，线性时间内遍历即可完成，当拓展到一般，如中位数时，相关算法就值得研究了。这里还要说明的是，排序解 决是一种平凡算法，但其复杂度是(Theta(nlogn)) 这次内容的主要知识点有：1.随机化版本的分治法求解&分析2.基于1的优化pivot选择的算法&am... 算法导论第九章 第K顺序统计量 weixin_33975951的博客 07-14 132 1.第K顺序统计量概念 　　在一个由n个元素组成的集合中，第k个顺序统计量是该集合中第k小的元素。例如，最小值是第1顺序统计量，最大值是第n顺序统计量。 2.求Top K元素与求第K顺序统计量不同 　　Top K元素：是指求数组中的最大（或者最小的）K个元素，一般K比较小，采用最大（或者最小）堆实现。之前写过的一篇有关文章是： 海量数据处理的 Top K算法(问题) 小顶堆实现 　　第K... 快速排序以及第k小元素的线性选择算法 weixin_33955681的博客 02-26 162 简要介绍下快速排序的思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。时间复杂度为O(nlogn) 一.《data structure and algorithm analysis in c》中的实现，测试过，觉得该说明的已经注释  C++... 算法：快速排序以及第k小元素的线性选择算法 Meditation 04-15 5828 简要介绍下快速排序的思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 一.《data structure and algorithm analysis in c》中的实现，测试过，觉得该说明的已经注释  C++ C 中位数与第K小元素 weixin_33991727的博客 11-19 129 算法实际上是模仿快速排序算法设计出来的，其基本思想也是对输入数组进行递归划分，与快速排序不同的是，它只对划分出来的子数组之一进行递归处理； int randompartition(int a[],int l,int r) { int i=l-1,j=r,v=a[r],tmp; for(;;) { while(a[++i]&lt;v); ... 求解第K小元素，找中位数 07-05 找中值和第k小元素，找出A[1...N]中第k小元素.找第K小元素 需要找中位数： 如果有偶数个，则找第n/2或n/2+1个小元素则可找到中位数； 如果有奇数个，则找第n/2+1个小元素则可找到中位数。 数理统计: 第一章 fengxuewei123的博客 12-21 2704 基本概念 简单随机样本的两个特征: 代表性, 独立性 378.有序矩阵中第K小的元素 l3_97504678的博客 09-25 386 378.有序矩阵中第K小的元素 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。 请注意，它是排序后的第k小元素，而不是第k个元素。 实例: 思路： 这个是二维数组，把二维数组转一维数组，然后排序找到最小的 代码 public int KthSmallest(int[,] matrix, int k) { //... 数组2——查找第k小元素 凌空的桨 12-08 1960 在数组a的前n个元素中找出第k（1≤k≤n）小的元素，例如，数组{98, 33, 21, 102, 45, 5, 32, 11, 65, 82, 193, 321, 34, 72}中第5小的元素是33。 【分析】 这是上海大学考研试题。要查找第k小的元素，并不需要完全对数组中的元素进行排序，可以利用快速排序算法思想，只对部分元素进行排序就可以找到第k小元素。 一趟排序结束后，若i==k，说明找... 算法代码实现之选出第k小元素、中位数、最小的k个元素(线性复杂度)，Golang(Go语言)实现 陈鹏万里 03-02 1170 封装成函数： //选出第k小元素，k为1~len(s)func SelectKthMin(s []int, k int) int { k-- lo, hi := 0, len(s)-1 for { j := partition(s, lo, hi) if j k { lo = j + 1 } else if j > k { hi = j - 1 } else { r “相关推荐”对你有帮助么？ 非常没帮助 没帮助 一般 有帮助 非常有帮助 提交 评论 被折叠的  条评论 为什么被折叠? 到【灌水乐园】发言 查看更多评论 添加红包 祝福语 请填写红包祝福语或标题 红包数量 个 红包个数最小为10个 红包总金额 元 红包金额最低5元 余额支付 当前余额3.43元 前往充值 > 需支付：10.00元 取消 确定 下一步 知道了 成就一亿技术人! hope_wisdom 发出的红包 打赏作者 fourye007 你的鼓励将是我创作的最大动力 ¥2 ¥4 ¥6 ¥10 ¥20 输入1-500的整数 余额支付 (余额：-- ) 扫码支付 扫码支付：¥2 获取中 扫码支付 您的余额不足，请更换扫码支付或充值 打赏作者 实付元 使用余额支付 点击重新获取 扫码支付 钱包余额 0 抵扣说明： 1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。 2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。 余额充值

最后

以上就是仁爱学姐为你收集整理的第k小元素（顺序统计量）的全部内容，希望文章能够帮你解决第k小元素（顺序统计量）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。