LeetCode第215题“数组中的第K个最大元素”要求找到未排序数组中第k个最大的元素。通常有几种常见的解决方案，包括使用排序、使用最小堆或快速选择算法。以下是这三种方法的详细C++实现：
方法一：使用排序
这种方法最为直观，先对数组进行排序，然后返回第k个最大的元素。
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), greater<int>());return nums[k - 1];}
};int main() {Solution solution;vector<int> nums = {3, 2, 1, 5, 6, 4};int k = 2;cout << "The " << k << "th largest element is " << solution.findKthLargest(nums, k) << endl;return 0;
}
方法二：使用最小堆
这种方法利用优先队列（最小堆），可以在O(NlogK)时间内找到第k个最大的元素。
#include <iostream>
#include <vector>
#include <queue>using namespace std;class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> minHeap;for (int num : nums) {minHeap.push(num);if (minHeap.size() > k) {minHeap.pop();}}return minHeap.top();}
};int main() {Solution solution;vector<int> nums = {3, 2, 1, 5, 6, 4};int k = 2;cout << "The " << k << "th largest element is " << solution.findKthLargest(nums, k) << endl;return 0;
}
方法三：快速选择算法
快速选择是一种高效的选择算法，平均时间复杂度为O(N)，最坏情况下为O(N^2)。
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
public:int findKthLargest(vector<int>& nums, int k) {return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);}private:int quickSelect(vector<int>& nums, int left, int right, int k) {if (left == right) return nums[left];int pivotIndex = partition(nums, left, right);if (k == pivotIndex) {return nums[k];} else if (k < pivotIndex) {return quickSelect(nums, left, pivotIndex - 1, k);} else {return quickSelect(nums, pivotIndex + 1, right, k);}}int partition(vector<int>& nums, int left, int right) {int pivot = nums[right];int storeIndex = left;for (int i = left; i < right; i++) {if (nums[i] < pivot) {swap(nums[storeIndex], nums[i]);storeIndex++;}}swap(nums[storeIndex], nums[right]);return storeIndex;}
};int main() {Solution solution;vector<int> nums = {3, 2, 1, 5, 6, 4};int k = 2;cout << "The " << k << "th largest element is " << solution.findKthLargest(nums, k) << endl;return 0;
}
选择合适的方法
- 如果数组较小且k值较大，排序方法（方法一）简单直接。
- 如果数组较大且需要高效处理，最小堆方法（方法二）和快速选择算法（方法三）更为适合。特别是快速选择算法在平均情况下时间复杂度较低，是处理大规模数据的较好选择。