题解 | #找到数组里的第k大数(C++)#

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int>& nums, int left, int right) {
    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]);
    return i + 1;
}

int quickSelect(vector<int>& nums, int left, int right, int k) {
    if (left == right) {
        return nums[left];
    }

    int pivotIndex = partition(nums, left, right);
    int rank = pivotIndex - left + 1;

    if (rank == k) {
        return nums[pivotIndex];
    } else if (rank > k) {
        return quickSelect(nums, left, pivotIndex - 1, k);
    } else {
        return quickSelect(nums, pivotIndex + 1, right, k - rank);
    }
}

int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();
    if (k <= 0 || k > n) {
        throw std::invalid_argument("Invalid k value");
    }

    return quickSelect(nums, 0, n - 1, n - k + 1); // 将k转换为第k大的位置
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    int kthLargest = findKthLargest(nums, k);
    cout << kthLargest << endl;

    return 0;
}

K选取问题，可以使用快速选择算法实现在不进行完全排序的情况下找到第k大的数。快速选择是一种改进的快速排序算法，它选择一个枢轴元素并根据其在排序后的位置来决定继续在左侧或右侧递归搜索，从而减少了排序的操作次数，时间复杂度为O(n)，需要注意这只在复杂度数量级上有意义，实际情况下常系数非常大，并且STL库中也给出了nth_element()的实现，比手动写出来更简单、复杂度更低。