如何用Python实现O(n)复杂度找出无序列表中第K大的元素？

本文共计2062个文字，预计阅读时间需要9分钟。

昨天面试上来就是一个算法，平时基本的算法还是行的，结果换个法子就不知道了。感觉应该刷一波Leecode冷静下。今天抽空看看。题目就是要求O(n)复杂度求无序序列中第K大元素。

昨天面试上来就是一个算法，平时基本的算法还行，结果变个法就不会了。。。感觉应该刷一波Leecode冷静下。。。今天抽空看下。

题目就是要求O(n)复杂度求无序列表中第K的大元素

如果没有复杂度的限制很简单。。。加了O(n)复杂度确实有点蒙

虽然当时面试官说思路对了，但是还是没搞出来，最后面试官提示用快排的思想

主要还是设立一个flag，列表中小于flag的组成左列表，大于等于flag的组成右列表，主要是不需要在对两侧列表在进行排序了，只需要生成左右列表就行，所以可以实现复杂度O(n)。

举个例子说明下步骤，比如有列表test_list=[6,5,4,3,2,1],找出第3大的元素，就是4，

如果flag=4:

l_list=[3,2,1]

r_list=[6,5]

因为第3大的元素，r_list长度为2，自然flag就是第3大的元素了，return flag，len(r_list)==k-1,就是结束递归的基线条件。