题目就是要求O(n)复杂度求无序列表中第K的大元素
如果没有复杂度的限制很简单。。。...举个例子说明下步骤,比如有列表test_list=[6,5,4,3,2,1],找出第3大的元素,就是4,
如果flag=4:
l_list=[3,2,1]
r_list=[6,5]
因为第3大的元素...=[]
相当于求l_list里第k-(len(test_list)-len(r_list)+1)大的元素了,这里就是相当于求l_list=[5,4,3,2,1]第2大的元素
通过这三种情况进行递归,...实际结果自然是n(1+1/2+1/4+1/8+….1/2ⁿ)=2n,复杂度自然就是O(n)了
最后实现代码如下:
#给定一个无序列表,求出第K大的元素,要求复杂度O(n)
def find_k(test_list...以上这篇Python要求O(n)复杂度求无序列表中第K的大元素实例就是小编分享给大家的全部内容了,希望能给大家一个参考。