目录【朴素方法】使用排序——时间复杂度为 O(n log(n))空间复杂度为 O(1)【预期方法】使用最大堆 - 时间复杂度为 O(n * log(k))空间复杂度为 O(k)【替代方案 1】使用快速选择【替代方案 2】使用计数排序如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定一个整数数组arr[]和元素个数k求数组中第 k 小的元素。注意k 始终小于数组的大小。例如输入arr[] [10, 5, 4, 3, 48, 6, 2, 33, 53, 10], k 4输出5说明给定数组中第四小的元素是 5。输入arr[] [7, 10, 4, 3, 20, 15], k 3输出7说明给定数组中第三小的元素是 7。【朴素方法】使用排序——时间复杂度为 O(n log(n))空间复杂度为 O(1)其思路是对给定的数组进行排序并返回索引 k - 1 处的元素。#includeiostream#include algorithm#includevectorusing namespace std;int kthSmallest(vectorint arr, int k){// Sort the given vectorsort(arr.begin(), arr.end());// Return kth element in the sorted vectorreturn arr[k - 1];}int main(){vectorint arr {10, 5, 4, 3, 48, 6, 2, 33, 53, 10};int k 4;cout kthSmallest(arr, k);return 0;}输出5【预期方法】使用最大堆 - 时间复杂度为 O(n * log(k))空间复杂度为 O(k)其思路是在遍历数组的过程中维护一个大小为 k 的最大堆。该堆始终包含目前为止遇到的 k 个最小元素。如果堆的大小超过 k则移除最大的元素。最终堆中只保留 k 个最小元素。#include iostream#include vector#include queueusing namespace std;int kthSmallest(vectorint arr, int k) {// Create a max heappriority_queueint pq;// Iterate through the array elementsfor (int i 0; i arr.size(); i){// Push the current element onto the max heappq.push(arr[i]);// If the size of the max heap exceeds k,//remove the largest elementif (pq.size() k)pq.pop();}return pq.top();}int main(){vectorint arr {10, 5, 4, 3, 48, 6, 2, 33, 53, 10};int k 4;cout kthSmallest(arr, k);}输出5【替代方案 1】使用快速选择主要思路是利用快速选择QuickSelect函数找到第 k 大元素。具体做法是选择一个基准元素然后将数组分割成多个部分使得大于基准元素的元素位于左侧小于基准元素的元素位于右侧。如果基准元素最终位于索引 k-1 处则该元素即为第 k 大元素。否则我们递归地仅在包含第 k 大元素的左侧或右侧部分进行搜索。#include iostream#include vectorusing namespace std;int partition(vectorint arr, int left, int right) {// Choose the last element as pivotint pivot arr[right];int i left;// Traverse the array and move elements pivot to the leftfor(int j left; j right; j) {if(arr[j] pivot) {// Swap current element with element at iswap(arr[i], arr[j]);i;}}// Place the pivot in its correct positionswap(arr[i], arr[right]);return i;}// QuickSelect function: recursively finds k-th smallestint quickSelect(vectorint arr, int left, int right, int k) {if(left right) {// Partition around pivotint pivotIndex partition(arr, left, right);// Found k-th smallestif(pivotIndex k) return arr[pivotIndex];else if(pivotIndex k)return quickSelect(arr, left, pivotIndex - 1, k);else return quickSelect(arr, pivotIndex 1, right, k);}return -1;}int kthSmallest(vectorint arr, int k) {return quickSelect(arr, 0, arr.size()-1, k-1);}int main() {vectorint arr {10,5,4,3,48,6,2,33,53,10};int k 4;cout kthSmallest(arr, k);}输出5时间复杂度 最坏情况下为O(n² )但平均时间为 O(n log n)且性能优于基于优先级队列的算法。辅助空间 最坏情况下递归调用栈为 O(n)。平均而言O(log n)。【替代方案 2】使用计数排序主要思路是利用计数排序的频率计数来跟踪有多少元素小于或等于每个值然后直接从这些累积计数中识别出第 K 小的元素而无需对数组进行完全排序。注意这种方法在元素范围较小时特别有效因为我们声明的数组大小为最大元素个数。如果元素范围非常大计数排序方法可能并非最有效的选择。#include iostream#include vectorusing namespace std;int kthSmallest(vectorint arr, int k) {// First, find the maximum element in the vectorint maxElement arr[0];for (int i 1; i arr.size(); i){if (arr[i] maxElement){maxElement arr[i];}}// Create an array to store the frequency of each elementvectorint freq(maxElement 1, 0);for (int i 0; i arr.size(); i){freq[arr[i]];}// Keep track of the cumulative frequency of elementsint count 0;for (int i 0; i maxElement; i){if (freq[i] ! 0){count freq[i];if (count k){// If we have seen k or more elements,// return the current elementreturn i;}}}return -1;}int main(){vectorint arr {10, 5, 4, 3, 48, 6, 2, 33, 53, 10};int k 4;cout kthSmallest(arr, k);return 0;}输出5时间复杂度 O(n maxElement)其中 maxElement 为数组中的最大元素。辅助空间 O(maxElement)。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。