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;
}

运行结果

Python要求O(n)复杂度求无序列表中第K的大元素实例

变形——从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;
}

运行结果

Python要求O(n)复杂度求无序列表中第K的大元素实例

变形——从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;
}

运行结果

Python要求O(n)复杂度求无序列表中第K的大元素实例

来源:https://blog.csdn.net/wenqiwenqi123/article/details/81669899

标签:Python,O(n),无序列表,K元素
0
投稿

猜你喜欢

  • MySQL五个查询优化方法

    2009-08-29 15:05:00
  • python的即时标记项目练习笔记

    2022-11-25 05:49:35
  • Mysql Binlog数据查看的方法详解

    2024-01-27 18:26:22
  • SQL Server 复制需要有实际的服务器名称才能连接到服务器

    2012-07-11 15:46:51
  • asp是的日期转换为星座的函数

    2011-02-26 11:11:00
  • 解决pycharm启动后总是不停的updating indices...indexing的问题

    2023-03-05 07:35:38
  • Python多分支if语句的使用

    2022-07-17 17:52:54
  • Python中GIL的使用详解

    2022-02-08 13:36:30
  • mysql创建表设置表主键id从1开始自增的解决方案

    2024-01-18 13:52:53
  • 提高CSS代码的可读性

    2008-05-11 18:59:00
  • keras 多任务多loss实例

    2022-09-21 12:49:33
  • 数据库访问性能优化

    2024-01-21 18:24:47
  • Go中的gRPC入门教程详解

    2024-02-22 13:56:36
  • Yii2 assets清除缓存的方法

    2024-05-13 09:51:47
  • python中的print()输出

    2023-06-27 18:07:03
  • 详解Go语言如何实现二叉树遍历

    2024-04-23 09:44:10
  • sql2000各个版本区别总结第1/3页

    2024-01-15 10:09:42
  • Python对象的属性访问过程详解

    2023-09-02 13:40:04
  • 解决Pytorch中的神坑:关于model.eval的问题

    2021-09-17 17:16:55
  • Golang reflect反射的使用实例

    2024-05-05 09:32:17
  • asp之家 网络编程 m.aspxhome.com