C++实现第k大与第k小元素查找（排序/堆/快速选择三方案）

```cpp #include <iostream> #include <vector> #include <algorithm> #include <queue> // 方法1：使用排序（简单直接） std::pair<int, int> findKthLargestAndSmallest_Sort(const std::vector<int>& a, int k) { if (k <= 0 || k > static_cast<int>(a.size())) { throw std::invalid_argument("k is out of valid range"); } std::vector<int> sorted = a; std::sort(sorted.begin(), sorted.end()); int kth_smallest = sorted[k - 1]; int kth_largest = sorted[sorted.size() - k]; return {kth_largest, kth_smallest}; } // 方法2：使用堆（更高效，时间复杂度 O(n log k)） std::pair<int, int> findKthLargestAndSmallest_Heap(const std::vector<int>& a, int k) { if (k <= 0 || k > static_cast<int>(a.size())) { throw std::invalid_argument("k is out of valid range"); } // 最小堆找第k大：维护大小为k的最小堆 std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap; for (int x : a) { min_heap.push(x); if (min_heap.size() > k) { min_heap.pop(); } } int kth_largest = min_heap.top(); // 最大堆找第k小：维护大小为k的最大堆 std::priority_queue<int> max_heap; for (int x : a) { max_heap.push(x); if (max_heap.size() > k) { max_heap.pop(); } } int kth_smallest = max_heap.top(); return {kth_largest, kth_smallest}; } // 方法3：使用快速选择（平均 O(n)，最优解） int quickSelect(std::vector<int>& nums, int left, int right, int k) { if (left == right) return nums[left]; int pivot_index = left + rand() % (right - left + 1); pivot_index = std::partition(nums, left, right, pivot_index); if (k == pivot_index) { return nums[k]; } else if (k < pivot_index) { return quickSelect(nums, left, pivot_index - 1, k); } else { return quickSelect(nums, pivot_index + 1, right, k); } } int partition(std::vector<int>& nums, int left, int right, int pivot_index) { int pivot_value = nums[pivot_index]; std::swap(nums[pivot_index], nums[right]); int store_index = left; for (int i = left; i < right; ++i) { if (nums[i] < pivot_value) { std::swap(nums[store_index], nums[i]); store_index++; } } std::swap(nums[right], nums[store_index]); return store_index; } std::pair<int, int> findKthLargestAndSmallest_QuickSelect(std::vector<int> a, int k) { if (k <= 0 || k > static_cast<int>(a.size())) { throw std::invalid_argument("k is out of valid range"); } int n = a.size(); // 第k大 = 第(n-k+1)小 int kth_largest = quickSelect(a, 0, n - 1, n - k); // 复制原数组用于找第k小 std::vector<int> b = a; int kth_smallest = quickSelect(b, 0, n - 1, k - 1); return {kth_largest, kth_smallest}; } int main() { // 示例用法 std::vector<int> a = {3, 2, 1, 5, 6, 4}; int k = 2; try { auto result1 = findKthLargestAndSmallest_Sort(a, k); std::cout << "Using sort:\n"; std::cout << "k-th largest: " << result1.first << "\n"; std::cout << "k-th smallest: " << result1.second << "\n\n"; auto result2 = findKthLargestAndSmallest_Heap(a, k); std::cout << "Using heap:\n"; std::cout << "k-th largest: " << result2.first << "\n"; std::cout << "k-th smallest: " << result2.second << "\n\n"; auto result3 = findKthLargestAndSmallest_QuickSelect(a, k); std::cout << "Using quick select:\n"; std::cout << "k-th largest: " << result3.first << "\n"; std::cout << "k-th smallest: " << result3.second << "\n"; } catch (const std::exception& e) { std::cerr << "Error: " << e.what() << std::endl; } return 0; } ``` 该代码提供了三种实现方式： - **排序法**：时间复杂度 O(n log n)，简洁易懂，适合小规模数据 - **堆方法**：时间复杂度 O(n log k)，空间 O(k)，适合 k 远小于 n 的场景 - **快速选择法**：平均时间复杂度 O(n)，最优化解，基于快排分治思想 所有函数均返回 `std::pair<int, int>`，其中 `first` 是第 k 大元素，`second` 是第 k 小元素。已包含边界检查和异常处理。 ######[AI问答 | 1294点数解答 | 2026-03-29 11:35:29]