c++寻找无序数组中的第K大元素

使用C++找到无序数组中的第K大元素的一种方法是通过快速选择算法（QuickSelect）。以下是一个简单的实现示例：

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

// 快速选择算法中的分区操作
int partition(std::vector<int>& nums, int low, int high) {
    int pivot = nums[high];
    int i = low - 1;

    for (int j = low; j < high; ++j) {
        if (nums[j] >= pivot) {
            ++i;
            std::swap(nums[i], nums[j]);
        }
    }

    std::swap(nums[i + 1], nums[high]);
    return i + 1;
}

// 使用快速选择算法找到第K大的元素
int quickSelect(std::vector<int>& nums, int low, int high, int k) {
    if (low <= high) {
        int pivotIndex = partition(nums, low, high);

        if (pivotIndex == k - 1) {
            return nums[pivotIndex];
        } else if (pivotIndex < k - 1) {
            return quickSelect(nums, pivotIndex + 1, high, k);
        } else {
            return quickSelect(nums, low, pivotIndex - 1, k);
        }
    }

    return -1; // 处理无效输入或越界情况
}

// 找到无序数组中的第K大元素
int findKthLargest(std::vector<int>& nums, int k) {
    int n = nums.size();
    if (k > 0 && k <= n) {
        return quickSelect(nums, 0, n - 1, k);
    }

    return -1; // 处理无效输入或越界情况
}

int main() {
    std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    int k = 3; // 第3大的元素

    int result = findKthLargest(nums, k);
    std::cout << "第 " << k << " 大的元素是：" << result << std::endl;

    return 0;
}

这段代码使用了快速选择算法，在数组中进行原地分区操作，直到找到第K大的元素。