快速选择算法 C++ 标准库函数：nth_element

‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者先看例题class Solution { public: int findKthLargest(vectorint nums, int k) { nth_element(nums.begin(), nums.end() - k, nums.end()); return nums[nums.size() - k]; } };对就是这么简单完了而且速度极快时间复杂度为O(n)下面仔细阐述一下这个库函数nth是n-th的缩写意思是第 n 个。拆解n表示一个整数序号th英语序数词后缀如 4th, 5th, 6th合起来 n-th第 n 个在函数名中的含义std::nth_element直译就是第 n 个元素。它的作用是把容器中如果完全排序后应该排在第 n 个位置的那个元素放到第 n 个位置。下标从0开始的哦作用把第二个参数表示的那个位置 应该排在那个位置的元素放过去且不保证其他元素有序。nth_element(nums.begin(), nums.end() - k, nums.end()); // ↑ ↑ ↑ // 起始迭代器 目标位置迭代器 结束迭代器nums.end() - k就是倒数第 k 个位置因为是升序排序倒数第 k 个位置就是第 k 大的元素所在的位置举例数组[3,2,1,5,6,4]k 2完全排序后是[1,2,3,4,5,6]第 2 大是 5在倒数第 2 个位置下标 4nth_element后数组变成类似[3,2,1,4,5,6]不唯一下标 4 的元素必定是 5复杂度维度复杂度时间平均 O(n)最坏 O(n²)但标准库通常用 Introselect 保证 O(n)空间O(1)其他语言的类似函数语言等价函数Cstd::nth_elementPythonheapq.nlargest(k, nums)[-1]或sorted(nums)[-k]JavaArrays.sort(nums); return nums[nums.length - k];