Python要求O(n)复杂度求无序列表中第K的大元素实例
作者:超屌的温jay 发布时间:2023-07-30 13:18:01
昨天面试上来就是一个算法,平时基本的算法还行,结果变个法就不会了。。。感觉应该刷一波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)
补充知识:从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
然后就枚举不了了,结束。
所以说,这样就可以避免判重了。
代码
#include<iostream>
#include<cstring>
using namespace std;
int n,k; //全局变量:从n个数的集合中选取k个数
int a[25]; //存放n个数的集合数据
int vis[25];//在dfs中记录数据是否被访问过
int re[25];//存放被选取的数字
void dfs(int step,int start)//参数step代表选取第几个数字,参数start代表从集合的第几个开始选
{
if(step==k)//如果选够了k个就输出
{
for(int i=0;i<k;i++)
{
cout<<re[i]<<" ";
}
cout<<endl;
}
for(int i=start;i<n;i++)//不降原则的核心步骤1:从第i+1个开始选取数字(避免重选)
{
if(vis[i]==1)
continue;
vis[i]=1;
re[step]=a[i];
dfs(step+1,i+1); //不降原则的核心步骤2:从第i+1个开始选取数字(避免重选)
vis[i]=0;
}
return;
}
int main()
{
while(cin>>n>>k)
{
memset(a,0,sizeof(a));
memset(re,0,sizeof(re));
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
cin>>a[i];
}
dfs(0,0);
}
return 0;
}
运行结果
变形——从N个数中选取k个数求和(举一反三)
代码
#include<iostream>
#include<cstring>
using namespace std;
int n,k; //全局变量:从n个数的集合中选取k个数
int a[25]; //存放n个数的集合数据
int vis[25];//在dfs中记录数据是否被访问过
int re[25];//存放被选取的数字
void dfs(int step,int sum,int start)//参数step代表选取第几个数字,参数sum代表从选取前step-1个数时的总数,参数start代表从集合的第几个开始选
{
if(step==k)//如果选够了k个就输出
{
cout<<re[0];
for(int i=1;i<k;i++)
{
cout<<'+'<<re[i];
}
cout<<'='<<sum<<endl;
}
for(int i=start;i<n;i++)//不降原则的核心步骤1:从第i+1个开始选取数字(避免重选)
{
if(vis[i]==1)
continue;
vis[i]=1;
re[step]=a[i];
dfs(step+1,sum+a[i],i+1); //不降原则的核心步骤2:从第i+1个开始选取数字(避免重选)
vis[i]=0;
}
return;
}
int main()
{
while(cin>>n>>k)
{
memset(a,0,sizeof(a));
memset(re,0,sizeof(re));
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
cin>>a[i];
}
dfs(0,0,0);
}
return 0;
}
运行结果
变形——从N个数中选取k个数求积(举一反三)
代码
#include<iostream>
#include<cstring>
using namespace std;
int n,k; //全局变量:从n个数的集合中选取k个数
int a[25]; //存放n个数的集合数据
int vis[25];//在dfs中记录数据是否被访问过
int re[25];//存放被选取的数字
void dfs(int step,int sum,int start)//参数step代表选取第几个数字,参数start代表从集合的第几个开始选
{
if(step==k)//如果选够了k个就输出
{
cout<<re[0];
for(int i=1;i<k;i++)
{
cout<<'*'<<re[i];
}
cout<<'='<<sum<<endl;
}
for(int i=start;i<n;i++)//不降原则的核心步骤1:从第i+1个开始选取数字(避免重选)
{
if(vis[i]==1)
continue;
vis[i]=1;
re[step]=a[i];
dfs(step+1,sum*a[i],i+1); //不降原则的核心步骤2:从第i+1个开始选取数字(避免重选)
vis[i]=0;
}
return;
}
int main()
{
while(cin>>n>>k)
{
memset(a,0,sizeof(a));
memset(re,0,sizeof(re));
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
cin>>a[i];
}
dfs(0,1,0);
}
return 0;
}
运行结果
来源:https://blog.csdn.net/wenqiwenqi123/article/details/81669899
猜你喜欢
- 本文实例讲述了PHP判断密码强度的方法。分享给大家供大家参考,具体如下:一、php页面$score = 0;if(!empty($_GET[
- python代码如下:import numpy as np# Write a function that takes as input a
- 这里的Counter是指collections中的Counter,通过Counter可以实现字典的创建以及字典key出现频次的统计。然而,使
- 近期接手越来越多的东西,发布和运维的工作相当机械,加上频率还蛮高,导致时间浪费还是优点多。修复bug什么的,测试,提交版本库(2分钟),ss
- 一、dict推导式list1 = ['name', 'age', 'gender']list
- 异步编程带来的问题在客户端Javascript中并不明显,但随着服务器端Javascript越来越广的被使用,大量的异步IO操作使得该问题变
- PDO::beginTransactionPDO::beginTransaction 启动一个事务(PHP 5 >= 5.1.0, P
- 随着网站访问量的加大,每次从数据库读取都是以效率作为代价的,很多用ACCESS作数据库的更会深有体会,静态页加在搜索时,也会被优先考虑。互联
- 好久没有写ASP代码了,今天在做一个简单的留言本时,出现了一下错误:Microsoft Office Access Database Eng
- 最近老板叫做一个数据查重的小练习,涉及从一个包含中文字段的文件中提取出其中的中文字段并存储,使用php开发。中间涉及到php正则表达式中文匹
- 在本人看来,HTML 5是一个妥协方案,虽不激进,但更能推动技术的继续进步。没有命名空间,元素也不要求闭合(当然这并不是优点),浏览器也可以
- 1、从数据库表中检索信息实际上,前面我们已经用到了SELECT语句,它用来从数据库表中检索信息。select语句格式一般为:SELECT 检
- instanceof 运算符 和 is_a() 方法都是判断:某对象是否属于该类 或 该类是此对象的父类(用于确定一个 PHP 变量是否属于
- 本文实例主要是对turtle的使用,实现Python+turtle动态绘制一棵树的实例,具体代码:# drawtree.pyfrom tur
- 问题描述:使用 SQL 2005 w/ SP2 的汇出汇入精灵将数据从 Access 汇入到 SQL2005 发生了错误,但使用在SQL 2
- 字体大小CSS2规范根据长度——水平和垂直尺寸——来定义字体。这个长度为一个数值,前面可能带一个可选的加(+)或减(-)标记符。另外,该数值
- 1. 用户必须在几秒钟知道网站是做什么的。注意力是因特网上最有价值的货币。 如果访问者无法在几秒钟之内得知你的网站的方向,他很有可能转而访问
- 前言每个人写脚本时的格式都会有所不同,有的会注明脚本本身的一些信息,有的则开门见山,这在小团队里其实没什么,基本别人做什么你也都知道,但如果
- 前言最近网站从HTTPS转为HTTP,更换了网址,旧网址做了301重定向,折腾有点大,于是在百度站长平台提交网址,不管是主动推送还是手动提交
- 本文实例讲述了Python tkinter模块弹出窗口及传值回到主窗口操作。分享给大家供大家参考,具体如下:有些时候,我们需要使用弹出窗口,