k选取是一个经典的算法问题，找到无序的数组中第k小的数（此处约定最小值为第一小的数）。很容易想到将数组排序，然后取出下标为k-1的元素，该算法的时间复杂度为。显然有更快的方法。
大顶堆法
一个大顶堆维护了弱序关系，堆顶为最大的元素。创建一个大顶堆，遍历数组，如果堆中的元素数量小于,则继续向堆中添加元素；如果堆中的元素数量恰为个，则将堆顶的元素与当前元素进行比较，若当前元素比堆顶小，则删除堆顶元素，将当前元素加入堆中；如果当前元素比堆顶大，则该元素不可能为第k小的数。代码如下：
#include <iostream>
#include <vector>
#include <queue>// header file for priority queue
using namespace std;
int kMinimumEle(vector<int> nums, int k) {
if (nums.empty() || k < 0 || k > nums.size()) return -1;
priority_queue<int> heap;
for (int i = 0; i < nums.size(); i++) {
if (heap.size() < k) heap.emplace(nums[i]);
else {
if (nums[i] < heap.top()) {
heap.pop();
heap.emplace(nums[i]);
}
}
}
return heap.top();
}
int main()
{
vector<int> nums = {5, 1, 3, 4, 9, 8, 8, 2};
for (int i = 1; i <= nums.size(); i++) {
cout << i << " : " << kMinimumEle(nums, i) << endl;
}
system("pause");
return 0;
}
运行结果：
1 : 1
2 : 2
3 : 3
4 : 4
5 : 5
6 : 8
7 : 8
8 : 9
由于堆的插入、删除操作的时间复杂度为,该算法的时间复杂度为,空间复杂度为.
划分(partition)
quicksort的基础就是对数组进行划分，选取一个轴点(主元),使得比轴点大的数位于左侧，比轴点大的数位于右侧。可以对数组进行划分，当轴点位置等于k-1时，正好找到第k小的元素；若轴点位置比k-1小，说明，第k小的元素在该轴点的右侧；反正在轴点的左侧，代码如下：
#include <iostream>
#include <vector>
#include <cstdlib>// header file for rand
#include <queue>// header file for priority queue
using namespace std;
int partition(vector<int>& nums, int low, int high) {
if (low < 0 || high >= nums.size() || low > high) return -1;
if (low == high) return low;
int index = low + rand() % (high - low + 1);
swap(nums[index], nums[low]);
int ele = nums[low];
while (low < high) {
while (high > low && (nums[high] >= ele)) high--;
nums[low] = nums[high];
while (low < high && (nums[low] <= ele)) low++;
nums[high] = nums[low];
}
nums[low] = ele;
return low;
}
int kMinimumEle(vector<int> nums, int k) {
k--;
if (nums.empty() || k < 0 || k > nums.size()) {
return -1;
}
int low = 0, high = nums.size() - 1;
int index = partition(nums, low, high);
while (index != k) {
if (index < k) low = index + 1;
else high = index - 1;
index = partition(nums, low, high);
}
return nums[index];
}
int main()
{
vector<int> nums = {5, 1, 3, 4, 9, 8, 8, 2};
for (int i = 1; i <= nums.size(); i++) {
cout << i << " : " << kMinimumEle(nums, i) << endl;
}
system("pause");
return 0;
}
运行结果与上述相同。由于在partition中，随机地选取元素作为轴点，所以从期望的角度，该算法的线性复杂度为。