本文内容主要介绍了python要求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,就是结束递归的基线条件。

如果flag=1:

l_list=[]

r_list=[6,5,4,3,2]

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

如果flag=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大的元素

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

最差复杂度就是n n-1 n-2 n-3 ...... 1=(1 n)n/2,就是O(n²)

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

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

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

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

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

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

最后实现代码如下:

python中如何求列表中最大元素(长篇文讲解Python要求O)(1)

补充知识:从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

2 3 5

2 3 6

2 4 5

2 4 6

2 5 6

就是这样的,枚举十分清晰,对吗?

以此类推…

3 4 5

3 4 6

3 5 6

4 5 6

然后就枚举不了了,结束。

所以说,这样就可以避免判重了。

代码:

python中如何求列表中最大元素(长篇文讲解Python要求O)(2)

运行结果:

python中如何求列表中最大元素(长篇文讲解Python要求O)(3)

变形——从N个数中选取k个数求和(举一反三)

代码:

python中如何求列表中最大元素(长篇文讲解Python要求O)(4)

python中如何求列表中最大元素(长篇文讲解Python要求O)(5)

运行结果:

python中如何求列表中最大元素(长篇文讲解Python要求O)(6)

变形——从N个数中选取k个数求积(举一反三)

代码

python中如何求列表中最大元素(长篇文讲解Python要求O)(7)

python中如何求列表中最大元素(长篇文讲解Python要求O)(8)

运行结果:

python中如何求列表中最大元素(长篇文讲解Python要求O)(9)

以上这篇Python要求O(n)复杂度求无序列表中第K的大元素实例就是小编分享给大家的全部内容了,更多相关内容关注小编敬请期待为你带来更优质的相关文章!

结尾

最后多说一句,小编是一名python开发工程师,这里有我自己整理了一套最新的python系统学习教程,包括从基础的python脚本到web开发、爬虫、数据分析、数据可视化、机器学习等。想要这些资料的可以关注小编,并在后台私信小编:“07”即可领取。

,