c++用分治法求k1-k2内的数

可以使用快速选择算法来解决这个问题，它是一种基于分治思想的算法。

具体步骤如下：

1. 选择一个元素作为枢轴（pivot），将小于枢轴的元素放在左边，大于枢轴的元素放在右边。

2. 如果枢轴的下标在k1到k2之间，则直接返回枢轴的值。

3. 如果枢轴的下标小于k1，则在右边的子数组中继续查找第k1-k2小的数。

4. 如果枢轴的下标大于k2，则在左边的子数组中继续查找第k1-k2小的数。

可以使用递归来实现该算法。具体实现代码如下：

int quickselect(vector<int>& nums, int left, int right, int k1, int k2) {
    int pivot = nums[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            i++;
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i + 1], nums[right]);
    int mid = i + 1;

    if (mid >= k1 && mid <= k2) {
        return nums[mid];
    } else if (mid < k1) {
        return quickselect(nums, mid + 1, right, k1, k2);
    } else {
        return quickselect(nums, left, mid - 1, k1, k2);
    }
}

vector<int> findKthNumbers(vector<int>& nums, int k1, int k2) {
    vector<int> result;
    int kth1 = quickselect(nums, 0, nums.size() - 1, k1 - 1, k2 - 1);
    int kth2 = quickselect(nums, 0, nums.size() - 1, k2 - 1, k2 - 1);
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] >= kth1 && nums[i] <= kth2) {
            result.push_back(nums[i]);
        }
    }
    return result;
}

其中，`nums`为输入数组，`k1`和`k2`为要查找的第k1小和第k2小的数的下标（从0开始）。调用`findKthNumbers`函数即可返回k1-k2内的数的集合。