Python怎么求无序列表中第K的大元素

本篇内容主要讲解“Python怎么求无序列表中第K的大元素”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Python怎么求无序列表中第K的大元素”吧!

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

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

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

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

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

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

<>强如果国旗=4:

l_list=(3,2,1)

r_list=(6,5)

因为第3大的元素,r_list长度为2,自然国旗就是第3大的元素了,返回国旗,len (r_list)==K - 1,就是结束递归的基线条件。

<>强如果标志=1:

l_list=[]

r_list=[6、5、4、3、2)

问题就变成了求r_list里面第K大的元素了

<>强如果国旗=6:

l_list=[5、4、3、2、1)

r_list=[]

相当于求l_list里第K - (len (test_list) len (r_list) + 1)大的元素了,这里就是相当于求l_list=[5、4、3、2、1)第2大的元素

通过这三种情况进行递归,最终返回旗就是目标元素

最差复杂度就是n + n - 1 + n + n +……+ 1=(1 + n) n/2,就是O (n& sup2)

当时我就会回答出了最差复杂度肯定是n& sup2;啊,面试小哥说平均复杂度,我说计算平均复杂度好像很复杂吧?感觉他也有点蒙,就说每次都是二分的情况的复杂度,

当时竟然回答了个logn * logn…最后还是被面试管提示的…太尴尬了…

实际上如果每次刚好二分,第一次取国旗比较次数是n,第二次是n/2,依次下去是n/4, 8 ..... n/n/2

就是n + n/2 + n/4 ....

最最丢人的是计算这个结果还想了一会…看样该做点高中上数学了…

实际结果自然是n (1 + 1/2 + 1/4 + 1/8 + .... 1/2 ?)=2 n,复杂度自然就是O (n)了

<强>最后实现代码如下:

#给定一个无序列表,求出第K大的元素,要求复杂度O (n) 　　def  find_k (test_list k): 　　,国旗=test_list [0] 　　,test_list.pop (0) 　　,l_list=[小姐:for 小姐:拷贝test_list  if 小姐:& lt;,国旗) 　　,r_list=[小姐:for 小姐:拷贝test_list  if 小姐:祝辞=,国旗) 　　, 　　,#结果递归的基线条件 　　,if  len (r_list)==k - 1: 　　return 才能;旗帜 　　,elif  len (r_list)在k - 1: 　　return 才能find_k (r_list k) 　　,其他的: 　　#因才能为test_list.pop(0)让test_list少了一个元素,所以下面需要+ 1 　　差距才能=len (test_list) len (l_list) + 1 　　k=k-gap才能 　　return 才能find_k (l_list k) 　　, 　　if  __name__ ==, & # 39; __main__ # 39;:=,test_list  [5,, 4,, 3,, 2,, 1, 10, 20100] 　　,res=find_k (test_list, 1) 　　,打印(res)

<强>补充知识: <强>从N个数选取k个数的组合,不降原则(DFS)

原理:不降原则(看代码前先看一下原理吧)

举个例子:

比如说在6里面随便选5个数,那么选法都是什么呢?

瞎枚举?

12345
12346

前两个还不会弄混

然后很可能就乱了

少点数可能不会乱

但是多了就不好整了

比如说在100年里随便选50个数。

1 2 3 4 5 6 7 8 9 10 11 12…

所以我们可以运用不降原则:

保证枚举的这些数是升序排列

其实真正的不降原则还可以平

比如1 2 2 3 3 4…

但是这里要说的“不降原则“不能平哦!

对于这道题也不能平

否则就有重复数字了

拿6个里面选3个举例子

1 2 3
1 2 4
1 2 5
1 2 6

第一轮枚举完毕。

第二个数加一

1 3 ?

这个“?”应该是4,因为是升序排列

1 3 4
1 3 5
1 3 6

接着,就是这样

1 4 5
1 4 6
1 5 6

<强>第一位是1枚举完毕

第一位是2呢?

2 3 4

Python怎么求无序列表中第K的大元素