寻找第k小的数c++

寻找数组中第k小的数是常见的算法问题，通常通过排序或特定的数据结构来解决。在C++中，有多种方法可以实现这个功能：

1. **排序 + 折半查找**：
- 先对数组进行排序（如快速排序、归并排序等），然后直接访问第k个元素。这种方法时间复杂度是O(n log n)。

#include <vector>
#include <algorithm>

int findKthSmallest(std::vector<int>& nums, int k) {
    std::sort(nums.begin(), nums.end());
    return nums[k - 1];
}

2. **最小堆（Priority Queue）**：
- 使用标准库中的`priority_queue`创建一个小顶堆，将前k个元素放入堆中。随后每次从堆中弹出最小元素，同时检查下一个元素是否应该替换堆顶元素。直到堆大小为k。这种方法时间复杂度是O(n log k)。

#include <queue>
#include <vector>

int findKthSmallest(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    for (size_t i = 0; i < k; ++i) {
        pq.push(nums[i]);
    }
    for (size_t i = k; i < nums.size(); ++i) {
        if (pq.top() > nums[i]) {
            pq.pop();
            pq.push(nums[i]);
        }
    }
    return pq.top();
}

3. **快速选择**：
- 是一种改进的快速排序算法，它只对找到第k小的元素的部分数据进行排序，而不是整个数组。平均时间复杂度为O(n)，但在最坏情况下仍然是O(n^2)。

4. **随机化**：
- 如果不想保证最优时间复杂度，可以采用随机抽样的方式，例如 reservoir sampling。这种方法适合大数据集，时间复杂度一般为线性O(n)。