本文共 1510 字,大约阅读时间需要 5 分钟。
昨天面试上来就是一个算法,平时基本的算法还行,结果变个法就不会了。。。感觉应该刷一波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)了
最后实现代码如下:
#给定一个无序列表,求出第K大的元素,要求复杂度O(n)def find_k(test_list,k): flag=test_list[0] test_list.pop(0) l_list=[i for i in test_list if i < flag] r_list=[i for i in test_list if i >= flag] #结果递归的基线条件 if len(r_list)==k-1: return flag elif len(r_list)>k-1: return find_k(r_list,k) else: #因为test_list.pop(0)让test_list少了一个元素,所以下面需要+1 gap=len(test_list)-len(l_list)+1 k=k-gap return find_k(l_list,k)if __name__ == '__main__': test_list = [5, 4, 3, 2, 1,10,20,100] res=find_k(test_list,1) print(res)
转载地址:http://rdxws.baihongyu.com/