C++实现的O(n)复杂度内查找第K大数算法示例

给定一个包含不同整数的未排序数组，以下是一个用C++实现的O(n)时间复杂度内查找第K大数的算法示例：

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

using namespace std;

int findKthLargest(vector<int>& nums, int k) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        // 选择一个随机的基准元素
        int pivotIndex = left + rand() % (right - left + 1);
        int pivot = nums[pivotIndex];

        // 将基准元素交换到数组末尾
        swap(nums[pivotIndex], 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]);

        // 根据K的值调整搜索范围
        if (i + 1 == k - 1) {
            return nums[i + 1];
        } else if (i + 1 < k - 1) {
            left = i + 2;
        } else {
            right = i;
        }
    }

    return -1; // 如果数组为空或K的值超出范围，则返回-1
}

int main() {
    vector<int> nums = {3, 1, 4, 2, 2, 6, 5};
    int k = 3;

    int result = findKthLargest(nums, k);
    
    if (result != -1) {
        cout << "第" << k << "大的数是: " << result << endl;
    } else {
        cout << "数组为空或K的值超出范围" << endl;
    }

    return 0;
}

此算法使用了快速选择算法的思想，通过每次将数组划分为两个部分，从而减少搜索的范围，最终找到第K大的数。