设计一个c++算法,使用分治法找出给定整数数组中第k大的数。

设计一个使用分治法解决这个问题的C++算法通常涉及快速选择（QuickSelect）的思想，这是一个改进版的快速排序算法，专门用于找到数组中的第k大元素，而不需要完全排序整个数组。

以下是一个简单的C++函数实现：

#include <vector>
#include <cstdlib>

// 随机化划分操作，使得算法平均时间复杂度为O(n)
int partition(std::vector<int>& nums, int left, int right, int k) {
    int pivot = nums[left + (right - left) / 2];
    while (left <= right) {
        while (nums[left] < pivot) left++;
        while (nums[right] > pivot) right--;
        if (left <= right) {
            std::swap(nums[left], nums[right]);
            left++;
            right--;
        }
    }
    return left == k ? nums[left] : nums[left] == nums[k] ? nums[left] : -1;
}

// 使用分治法查找第k大的元素
int findKthLargest(std::vector<int>& nums, int k) {
    if (nums.empty() || k < 1 || k > nums.size()) {
        throw std::invalid_argument("Invalid input");
    }
    return findKthLargestHelper(nums, 0, nums.size() - 1, k);
}

// 辅助函数：递归查找第k大的元素
int findKthLargestHelper(const std::vector<int>& nums, int left, int right, int k) {
    if (left == right) { // 只有一个元素，肯定是最大的
        return nums[left];
    } else if (left == right - 1) { // 只有两个元素，简单比较
        return nums[left] > nums[right] ? nums[left] : nums[right];
    } else {
        int pivotIndex = partition(nums, left, right, k);
        if (pivotIndex == k - 1) {
            return nums[pivotIndex];
        } else if (pivotIndex < k - 1) {
            return findKthLargestHelper(nums, pivotIndex + 1, right, k);
        } else {
            return findKthLargestHelper(nums, left, pivotIndex - 1, k);
        }
    }
}