C++ 第k个最小元素(K’th Smallest Element)
目录
【朴素方法】使用排序——时间复杂度为 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 处的元素。
#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
int kthSmallest(vector<int>& arr, int k)
{
// Sort the given vector
sort(arr.begin(), arr.end());
// Return k'th element in the sorted vector
return arr[k - 1];
}
int main()
{
vector<int> 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 <queue>
using namespace std;
int kthSmallest(vector<int>& arr, int k) {
// Create a max heap
priority_queue<int> pq;
// Iterate through the array elements
for (int i = 0; i < arr.size(); i++)
{
// Push the current element onto the max heap
pq.push(arr[i]);
// If the size of the max heap exceeds k,
//remove the largest element
if (pq.size() > k)
pq.pop();
}
return pq.top();
}
int main()
{
vector<int> 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 <vector>
using namespace std;
int partition(vector<int>& arr, int left, int right) {
// Choose the last element as pivot
int pivot = arr[right];
int i = left;
// Traverse the array and move elements <= pivot to the left
for(int j = left; j < right; j++) {
if(arr[j] <= pivot) {
// Swap current element with element at i
swap(arr[i], arr[j]);
i++;
}
}
// Place the pivot in its correct position
swap(arr[i], arr[right]);
return i;
}
// QuickSelect function: recursively finds k-th smallest
int quickSelect(vector<int>& arr, int left, int right, int k) {
if(left <= right) {
// Partition around pivot
int pivotIndex = partition(arr, left, right);
// Found k-th smallest
if(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(vector<int>& arr, int k) {
return quickSelect(arr, 0, arr.size()-1, k-1);
}
int main() {
vector<int> 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 <vector>
using namespace std;
int kthSmallest(vector<int>& arr, int k) {
// First, find the maximum element in the vector
int 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 element
vector<int> freq(maxElement + 1, 0);
for (int i = 0; i < arr.size(); i++)
{
freq[arr[i]]++;
}
// Keep track of the cumulative frequency of elements
int 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 element
return i;
}
}
}
return -1;
}
int main()
{
vector<int> 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)。
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。