给你一个总个数为n的数组a，并且一个数字k，请你求出这个数组中的第k小的数字（注意：给出的数组不保证是有序的）。第k小的定义是在这数组中从小到大的第k个。 注意请使用O(n)时间复杂度的算法进行 这里输入数据过大，请使用scanf读入并给出c++代码

这个问题可以用快速选择（QuickSelect）算法来解决，这是一种基于快速排序的在平均情况下时间复杂度为O(n)的选择算法。它的基本思想是通过一趟扫描，确定数组中某个元素（即目标值k）的位置，而不是像快速排序那样完全排序整个数组。

下面是C++代码实现：

#include <vector>
#include <algorithm>
#include <cstdlib>

int partition(std::vector<int>& nums, int low, int high, int pivotIndex) {
    int pivotValue = nums[pivotIndex];
    swap(nums[pivotIndex], nums[high]); // 将pivot放在最后
    int storeIndex = low - 1;
    for (int i = low; i < high; ++i) {
        if (nums[i] < pivotValue) {
            ++storeIndex;
            swap(nums[i], nums[storeIndex]);
        }
    }
    swap(nums[high], nums[storeIndex + 1]); // 将pivot放回正确的位置
    return storeIndex + 1;
}

int quickSelect(std::vector<int>& nums, int low, int high, int k) {
    if (low == high) {
        return nums[low]; // 只有一个元素的情况
    }
    int pivotIndex = rand() % (high - low + 1) + low; // 随机选取分区点
    pivotIndex = partition(nums, low, high, pivotIndex);
    if (k == pivotIndex) {
        return nums[k]; // 找到了第k小的元素
    } else if (k < pivotIndex) {
        return quickSelect(nums, low, pivotIndex - 1, k); // 在左半边查找
    } else {
        return quickSelect(nums, pivotIndex + 1, high, k); // 在右半边查找
    }
}

int findKthSmallestNumber(std::vector<int>& nums, int k) {
    return quickSelect(nums, 0, nums.size() - 1, k - 1); // 由于数组索引从0开始，所以k-1对应的是第k小的元素
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    int result = findKthSmallestNumber(a, k);
    printf("The %dth smallest number is: %d\n", k, result);
    return 0;
}

这个程序首先从数组中随机选择一个元素作为枢轴，然后通过分区操作将数组分为两部分，使得左边的元素都小于枢轴，右边的元素都大于等于枢轴。然后根据k与枢轴位置的关系递归地在左半边或右半边查找，直到找到第k小的元素。