给定元素值互异的数组 A[1…n]，尝试在 O(n) 时间内找到最小的 k 个数,算法设计C++代码

可以使用快速选择算法来解决这个问题，其时间复杂度为 O(n)。

具体步骤如下：

1. 选取数组 A 中的一个随机元素 x，把数组 A 分为两个部分：小于 x 的元素放在左边，大于等于 x 的元素放在右边。

2. 如果左半部分的元素个数小于 k，则在右半部分递归寻找最小的 k - 左半部分元素个数 个元素。

3. 如果左半部分的元素个数大于等于 k，则在左半部分递归寻找最小的 k 个元素。

4. 如果左半部分的元素个数恰好等于 k，则左半部分的所有元素都是最小的 k 个元素。

C++代码实现如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int quickSelect(vector<int>& nums, int k, int left, int right) {
    int pivot = nums[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;
        nums[i] = nums[j];
        while (i < j && nums[i] < pivot) i++;
        nums[j] = nums[i];
    }
    nums[i] = pivot;
    if (i - left == k - 1) return i;
    else if (i - left > k - 1) return quickSelect(nums, k, left, i - 1);
    else return quickSelect(nums, k - i + left - 1, i + 1, right);
}

vector<int> findKSmallest(vector<int>& nums, int k) {
    int index = quickSelect(nums, k, 0, nums.size() - 1);
    vector<int> res;
    for (int i = 0; i <= index; i++) {
        res.push_back(nums[i]);
    }
    return res;
}

int main() {
    vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;
    vector<int> res = findKSmallest(nums, k);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    return 0;
}