std::nth_element的原理与用途
解释std::nth_element算法的工作原理、时间复杂度和实际用途。它和partial_sort有何区别？如何在O(n)时间内找到第k大元素？
回答
孤独的心
std::nth_element(first, nth, last)以O(n)的期望复杂度重排范围，使得nth指向的元素等于全排序后该位置的元素，且左边都≤它、右边都≥它（不完全排序）。实现基于IntroSelect（快速选择的改进版）：选择pivot分区→根据k所在区间递归→递归深度过大时降级为堆选择保证O(n)最坏情况。与partial_sort的区别：partial_sort(O(n log k))将前k个元素排序好，nth_element只保证nth处是正确的而不排序两侧。用途：求中位数、TOP-K问题（配合partition做进一步排序）、数据流分位数计算。注意：需要随机访问迭代器，vector可用但list不可用。