c++ 给定一个数组，要求找出数组中第k小的元素

在 C++ 中，找到数组中第 k 小的元素可以使用多种算法，例如快速选择、堆排序、分治法等。这里简单介绍一种基于快速选择思想的解决方案，它的时间复杂度在平均情况下接近 O(n)：

#include <vector>
#include <algorithm>

int findKthSmallest(std::vector<int>& nums, int k) {
    if (nums.empty() || k < 1 || k > nums.size()) {
        return -1; // 非法输入处理
    }
    
    // 使用快速选择
    return quickSelect(nums, 0, nums.size() - 1, k);
}

// 快速选择函数，通过划分操作找到第 k 小的元素
int quickSelect(std::vector<int>& nums, int left, int right, int k) {
    if (left == right) { // 只有一个元素的情况
        return nums[left];
    }

    int pivotIndex = partition(nums, left, right); // 找到基准点的索引
    if (k == pivotIndex) {
        return nums[k]; // 基准点就是第 k 小的元素
    } else if (k < pivotIndex) {
        return quickSelect(nums, left, pivotIndex - 1, k);
    } else {
        return quickSelect(nums, pivotIndex + 1, right, k);
    }
}

// 基于 Lomuto 分区的辅助函数
int partition(std::vector<int>& nums, int left, int right) {
    int pivot = nums[right]; // 选择最右边作为基准
    int i = left;
    for (int j = left; j < right; ++j) {
        if (nums[j] < pivot) {
            std::swap(nums[i], nums[j]);
            i++;
        }
    }
    std::swap(nums[i], nums[right]); // 将基准放到正确的位置
    return i;
}