C++ 未排序数组中第 k 个最小/最大元素 | 最坏情况下的线性时间-北京尧图网络

目录例如方法实现上述想法的步骤示例代码详细时间复杂度分析递推关系式变为代入递推式结论如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。未排序数组中第 k 个最小/最大元素 | 最坏情况下的线性时间(K’th Smallest/Largest Element in Unsorted Array | Worst case Linear Time)给定一个包含不同整数的数组arr[]和一个整数k。任务是找出数组中第 k 小的元素。为了便于理解 k指的是如果将数组按升序排列则位于第 k 个位置的元素。注意 k 始终小于数组的大小。例如输入arr[] [7, 10, 4, 3, 20, 15], k 3输出7说明排序后的数组为 [3, 4, 7, 10, 15, 20]。第三小的元素是 7。输入arr[] [12, 3, 5, 7, 19], k 2输出5说明排序后的数组为 [3, 5, 7, 12, 19]。第二小的元素是 5。输入arr[] [1, 5, 2, 8, 3], k 4输出5在之前的“未排序数组中第 k 个最小/最大元素预期线性时间”文章中我们探讨了一种预期时间复杂度为线性的算法。本文将讨论一种最坏情况下时间复杂度为线性的方法。未排序数组中第 k 个最小/最大元素预期线性时间C 未排序数组中第 k 个最小/最大元素预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051233C# 未排序数组中第 k 个最小/最大元素预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051552Java 未排序数组中第 k 个最小/最大元素预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051446Python 未排序数组中第 k 个最小/最大元素预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051495JavaScript 未排序数组中第 k 个最小/最大元素预期线性时间 https://blog.csdn.net/hefeng_aspnet/article/details/163051600方法这段代码的思路与QuickSelect()函数的基本思想相同都是通过围绕一个枢轴点对数组进行分区来找到第 k 小的元素。但与 QuickSelect() 不同的是QuickSelect() 可能会选择不好的枢轴点导致最坏情况下的时间复杂度降至O(n²)而该算法通过使用“中位数的中位数”技术精心选择枢轴点确保了最坏情况下的线性时间复杂度。我们希望枢轴点能够保证分区的合理平衡并非完全平衡但也并非极度偏斜。这意味着枢轴点应该确保数组的大部分都位于其两侧。这就是“中位数的中位数”策略的作用所在。实现上述想法的步骤1、为了找到合适的枢轴点我们将数组分成每组5 个元素。这个大小5是一个关键的观察结果它既足够小可以实现快速排序又足够大可以确保在划分过程中达到数学上可证明的平衡。2、每个组独立排序并将其中位数收集到一个名为“中位数”的新列表中。3、收集完所有中位数后我们递归地找到这个中位数列表的中位数。这个值就成为我们的枢轴值。这样做的目的是为了避免使用错误的枢轴值使其尽可能接近整个数组的真实中位数。4、确定枢轴点后我们使用标准逻辑对数组进行分区左移元素小于等于枢轴点右移元素大于枢轴点。函数 partitionAroundPivot() 将枢轴点移动到正确的位置并返回该位置。5、现在我们将这个枢轴点的位置与所需的第 k 个索引进行比较。如果匹配则直接返回该值作为答案。6、否则我们决定是在枢轴的左侧还是右侧进行递归6.1、如果枢轴位于第 k 个位置之后则答案位于左侧子数组中。6.2、如果枢轴位于第 k 个位置之前则相应地调整 k并对右侧子数组递归。示例代码// C implementation of the Worst Case Linear Time algorithm// to find the k-th smallest element using Median of Medians#include bits/stdc.husing namespace std;// Returns median of a small group (size 5)int getMedian(vectorint group) {sort(group.begin(), group.end());return group[group.size() / 2];}// Function to Partition array from index// l to r around the pivot value xint partitionAroundPivot(vectorint arr,int l, int r, int x) {// Move pivot x to endint i;for (i l; i r; i) {if (arr[i] x) break;}swap(arr[i], arr[r]);// Standard partition logici l;for (int j l; j r; j) {if (arr[j] x) {swap(arr[i], arr[j]);i;}}swap(arr[i], arr[r]);// Final position of pivotreturn i;}// Recursively finds the k-th smallest element in arr[l..r]int selectKthSmallest(vectorint arr, int l, int r, int k) {if (k 0 k r - l 1) {int n r - l 1;vectorint medians;int i;// Divide array into groups of 5 and store their mediansfor (i 0; i n / 5; i) {vectorint group(arr.begin() l i * 5,arr.begin() l i * 5 5);medians.push_back(getMedian(group));}// Handle the last group with less than 5 elementsif (i * 5 n) {vectorint lastGroup(arr.begin() l i * 5,arr.begin() l i * 5 (n % 5));medians.push_back(getMedian(lastGroup));}// Find median of mediansint pivot;if (medians.size() 1) {pivot medians[0];} else {pivot selectKthSmallest(medians, 0, medians.size() - 1,medians.size() / 2);}// Partition array and get position of pivotint pos partitionAroundPivot(arr, l, r, pivot);// If position matches k, return resultif (pos - l k - 1) return arr[pos];// Recur on left or right part accordinglyif (pos - l k - 1)return selectKthSmallest(arr, l, pos - 1, k);return selectKthSmallest(arr, pos 1, r, k - pos l - 1);}return INT_MAX;}// Function to find kth Smallest in Arrayint kthSmallest(vectorint arr, int k) {return selectKthSmallest(arr, 0, arr.size() - 1, k);}// Driver codeint main() {vectorint arr {7, 10, 4, 3, 20, 15};int k 3;cout kthSmallest(arr, k);return 0;}输出7时间复杂度O(n)最坏情况下选择时间为线性时间空间复杂度O(n)在每次选择调用中递归存储中位数需要额外的空间。详细时间复杂度分析我们逐步分析中位数算法的最坏情况时间复杂度1、将数组分成 5 个元素一组的组。共有 n/5 组这样的组。由于每组元素的大小是固定的因此求每组的中位数需要O(1) 的时间。所以这一步的总时间复杂度为O(n)。2、求中位数的中位数。递归地求 n/5 个中位数的中位数需要T(n/5)时间。3、使用标准分区操作围绕枢轴中位数的中位数对数组进行分区需要O(n)时间。4、划分完成后递归调用会根据第 k 个最小元素所在的位置向一侧左侧或右侧进行。为了解递归调用的规模我们分析有多少元素保证大于或小于枢轴值。n/5 个中位数中至少有一半大于或等于中位数的中位数。每一组中位数至少贡献 3 个大于中位数的中位数的元素。因此大于或等于枢轴值的元素个数至少为(3 * ceil(1/2 * ceil(n/5)) - 6)即至少为(3n/10 - 6)。类似地小于枢轴值的元素个数至少为 3n/10 - 6。因此在最坏的情况下递归调用最多会处理 n - (3n/10 - 6) 7n/10 6 个元素。递推关系式变为当 n 80 时T(n) Θ(1)当n 80 时T(n) T(ceil(n/5)) T(7n/10 6) O(n)。我们通过代换法证明 T(n) O(n)。假设对于某个常数 c对于所有 n 80都有 T(n) cn。代入递推式T(n) c(n/5) c(7n/10 6) O(n) cn/5 7cn/10 6c O(n) 9cn/10 6c O(n)我们可以选择足够大的 c使得 cn/10 6c O(n)因此 T(n) cn。因此最坏情况下的运行时间是线性的O(n)。结论尽管该算法在最坏情况下是线性的但由于递归开销和多次迭代涉及的常数项很大。实际上随机化的快速选择算法速度更快尽管其性能仅针对平均情况但通常仍是首选。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。

C++ 未排序数组中第 k 个最小/最大元素 | 最坏情况下的线性时间

相关推荐

iToF vs dToF：从相位测距到光子计时，深度感知技术怎么选？

RAG大文件处理与并发优化实践：从解析到生成的全链路性能提升

Remotion 图片处理完全指南：从 `＜Img＞` 布局定位到 `getImageDimensions` 动态取图

更多资讯

天津电工证价格揭秘：真实经历告诉你怎么避坑

低压电工证绍兴官方回应：外省证书怎么转过来？实操干货全在这

防城港学电工证报名怎么搞？网上查询教你一步步搞定

天津电工证价格最新政策解读：证书过期了不知道怎么复审延期？多久拿证别踩坑

考低压电工证有学校吗？外省证书能转吗？电子证书怎么查

考取焊工电工证的条件有哪些？考前押题帮你一次过！

今日更新

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

相关推荐

iToF vs dToF：从相位测距到光子计时，深度感知技术怎么选？

RAG大文件处理与并发优化实践：从解析到生成的全链路性能提升

Remotion 图片处理完全指南：从 `＜Img＞` 布局定位到 `getImageDimensions` 动态取图

更多资讯

天津电工证价格揭秘：真实经历告诉你怎么避坑

低压电工证绍兴官方回应：外省证书怎么转过来？实操干货全在这

防城港学电工证报名怎么搞？网上查询教你一步步搞定

天津电工证价格最新政策解读：证书过期了不知道怎么复审延期？多久拿证别踩坑

考低压电工证有学校吗？外省证书能转吗？电子证书怎么查

考取焊工电工证的条件有哪些？考前押题帮你一次过！

今日更新

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

新疆电工作业干活累吗良心建议助你避开考不过的坑

新疆电工作业干活累吗良心建议助你避开考不过的坑