C++ 未排序数组中第 k 个最小/最大元素 （预期线性时间）

目录例如流程图示例代码参考资料如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。未排序数组中第 k 个最小/最大元素 预期线性时间(Kth Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time))给定一个数组和一个小于数组大小的数 k我们需要找到数组中第 k 大的元素。已知数组中的所有元素都互不相同。建议您先阅读以下文章然后再阅读本文第k个最小元素C 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163050624C# 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163051124Java 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163050998Python 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163051049JavaScript 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163051180例如输入arr[] {7, 10, 4, 3, 20, 15}k 3输出7输入arr[] {7, 10, 4, 3, 20, 15}k 4输出10在上面的文章(第k个最小元素)中讨论了三种不同的解决方案。本文将讨论方法 4它主要是对上面的文章(第k个最小元素)中讨论的方法 3快速选择的扩展。流程图示例代码// C program of above implementation#include bits/stdc.husing namespace std;// Standard partition process of QuickSort().// It considers the last element as pivot and// oves all smaller element to left of it// and greater elements to rightint partition(int* arr, int l, int r){int x arr[r], i l;for (int j l; j r - 1; j) {if (arr[j] x) {swap(arr[i], arr[j]);i;}}swap(arr[i], arr[r]);return i;}int randomPartition(int* arr, int l, int r){int n r - l 1;int pivot (rand() % 100 1) % n;swap(arr[l pivot], arr[r]);return partition(arr, l, r);}// This function returns kth smallest// element in arr[l..r] using// QuickSort based method. ASSUMPTION:// ALL ELEMENTS IN ARR[] ARE DISTINCTint kthSmallest(int* arr, int l, int r, int k){// If k is smaller than number// of elements in arrayif (k 0 k r - l 1) {// Partition the array around last// element and get position of pivot// element in sorted arrayint pos randomPartition(arr, l, r);// If position is same as kif (pos - l k - 1) {return arr[pos];}// If position is more, recur// for left subarrayif (pos - l k - 1) {return kthSmallest(arr, l, pos - 1, k);}// Else recur for right subarrayreturn kthSmallest(arr, pos 1, r,k - pos l - 1);}// If k is more than number of// elements in arrayreturn INT_MAX;}// Driver Codeint main(){int arr[] { 12, 3, 5, 7, 4, 19, 26 };int n sizeof(arr) / sizeof(arr[0]), k 3;cout Kth smallest element is kthSmallest(arr, 0, n - 1, k);}输出Kth smallest element is 5时间复杂度 O(N * log N)。辅助空间 O(1)。参考资料C 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163050624C# 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163051124Java 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163050998Python 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163051049JavaScript 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163051180如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。