C++ 中的第 K 大元素

Source: Dev.to

🧩 问题描述

给定一个数组和一个整数 k，找出第 k 大的元素。

示例

• 输入: [3, 2, 1, 5, 6, 4], k = 2
• 输出: 5

🧠 我的第一想法：单遍 + 贪心更新

许多数组问题可以通过以下方式解决：

• 一次循环
• 常数空间
• 贪心更新

我问自己：“能否在一次遍历中跟踪第 k 大的元素？”

尝试的思路（贪心思考）

• 不断更新最大的值。
• 尝试动态维护第 k 大的元素。

❌ 为什么会失败

要找第 k 大的元素，需要知道有多少元素比当前值更大。在单遍遍历中：

• 不了解后面的元素。
• 无法准确决定排名。
• 贪心决策变得不可靠。

📌 关键洞察

只有当局部决策能够保证全局正确性时，贪心才有效。

贪心失效的例子

数组: {7, 4, 6, 3, 9, 1}, k = 2

遍历时你可能会认为 7 已经很大，但随后出现的 9 会改变排名。之前的贪心决策因此失效。排名问题依赖完整的上下文，而不是部分遍历。

🧠 重要收获

✅ 正确做法：使用 STL sort()

#include 
#include 
#include 
using namespace std;

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

    sort(arr.begin(), arr.end(), greater());

    cout << "Kth largest element: " << arr[k - 1];
}

⏱ 时间与空间复杂度

• 排序: O(n log n)
• 空间: 原地排序 O(1)（不计递归栈）

在大多数面试题中，这已经足够，除非约束非常大。

⚠️ 但排序总是最优吗？

• 对于大数据集:
  • priority_queue → O(n log k)
  • nth_element → 平均 O(n)

在学习和面试中，sort() 的优势在于：

• 可读性强
• 可靠
• 易于解释

🧠 面试思考的教训（最重要）

解决问题时，问自己：

1. 该问题是否需要 全局排序？
2. 局部贪心决策 能否保证正确性？

如果答案是 否，请记住：“优化应在正确之后进行。”

🚀 最终收获

• 尝试了贪心 → 理解了其局限。
• 使用 STL sort() → 得到正确、简洁的解法。
• 学会了何时 不 进行优化。

这才是真正的进步。

📝 练习建议

使用以下检查表对问题进行分类：

• ✅ 可以用贪心单遍解决？
• ✅ 需要排序？
• ✅ 需要堆？

养成这种习惯可以提升面试思考的速度。