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)了

最后实现代码如下:

#给定一个无序列表,求出第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;
}

运行结果

以上这篇Python要求O(n)复杂度求无序列表中第K的大元素实例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • Python实现从N个数中找到最大的K个数

    提出问题: 如何在某集合里面找出最大或最小的K个元素. 解决思路: 找出最大或最下的K个元素,可以使用Python库中的heapq模块,该模块提供两个函数nlargest()求最大K个和nsmallest()求最小K个. 下面我们举例说明: import heapq nums=[12,-9,-3,32,9,56,23,0,11,34] print(heapq.nlargest(4,nums)) #-->最大的4个 print(heapq.nsmallest(4,nums)) #-->最小的4个

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

    昨天面试上来就是一个算法,平时基本的算法还行,结果变个法就不会了...感觉应该刷一波Leecode冷静下...今天抽空看下. 题目就是要求O(n)复杂度求无序列表中第K的大元素 如果没有复杂度的限制很简单...加了O(n)复杂度确实有点蒙 虽然当时面试官说思路对了,但是还是没搞出来,最后面试官提示用快排的思想 主要还是设立一个flag,列表中小于flag的组成左列表,大于等于flag的组成右列表,主要是不需要在对两侧列表在进行排序了,只需要生成左右列表就行,所以可以实现复杂度O(n). 举个例子

  • python 求一个列表中所有元素的乘积实例

    如下所示: # 求一个列表中所有元素的乘积 from functools import reduce lt = [1,2,3,4,5] ln = reduce(lambda x,y:x * y,lt) print(ln) 以上这篇python 求一个列表中所有元素的乘积实例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • Python实现删除列表中满足一定条件的元素示例

    本文实例讲述了Python实现删除列表中满足一定条件的元素.分享给大家供大家参考,具体如下: 从列表中删除满足一定条件的元素. 如:删除一个列表中长度为0的元素,或者删除列表中同时是2和3的倍数的元素. 做过高级语言编程的人想当然的会认为"这很简单",可以如下面的方式来实现: for i in listObj: if(...): listObj.remove(i) 看下一个小例子和结果: a = [1, 2, 3, 12, 12, 5, 6, 8, 9] for i in a: if

  • python 实现返回一个列表中出现次数最多的元素方法

    如下所示: # 返回一个列表中出现次数最多的元素 def showmax(lt):     index1 = 0                       #记录出现次数最多的元素下标     max = 0                          #记录最大的元素出现次数     for i in range(len(lt)):         flag = 0                    #记录每一个元素出现的次数         for j in range(i+1,

  • Python list列表中删除多个重复元素操作示例

    本文实例讲述了Python list列表中删除多个重复元素操作.分享给大家供大家参考,具体如下: 我们以下面这个list为例,删除其中所有值为6的元素: l=[9,6,5,6,6,7,8,9,6,0] 首先尝试remove方法: l.remove(6) print(l) 结果为:[9, 5, 6, 6, 7, 8, 9, 6, 0],只删除了第一个为6的元素. 如果采用for循环遍历各元素: for x in l: if x == 6: l.remove(x) 结果为[9, 5, 7, 8, 9

  • Python 找到列表中满足某些条件的元素方法

    如下所示: a = [0, 1, 2, 3, 4, 0, 2, 3, 6, 7, 5] selected = [x for x in a if x in range(1, 5)] # 找到a中属于[1,5)中的元素 print selected 以上这篇Python 找到列表中满足某些条件的元素方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • Python找出列表中出现次数最多的元素三种方式

    通过三种方式给大家介绍,具体详情如下所示: 方式一: 原理:创建一个新的空字典,用循环的方式来获取列表中的每一个元素,判断获取的元素是否存在字典中的key,如果不存在的话,将元素作为key,值为列表中元素的count # 字典方法 words = [ 'my', 'skills', 'are', 'poor', 'I', 'am', 'poor', 'I', 'need', 'skills', 'more', 'my', 'ability', 'are', 'so', 'poor' ] dict

  • 在Python的列表中利用remove()方法删除元素的教程

    remove()方法从列表中删除第一个obj. 语法 以下是remove()方法的语法: list.remove(obj) 参数 obj -- 这是可以从列表中移除该对象 返回值 此方法不返回任何值,但从列表中删除给定的对象 例子 下面的例子显示了remove()方法的使用 #!/usr/bin/python aList = [123, 'xyz', 'zara', 'abc', 'xyz']; aList.remove('xyz'); print "List : ", aList;

  • python中使用enumerate函数遍历元素实例

    这个是python的一个内建函数,看书的时候发现了他,mark一下当我们既需要遍历索引同时需要遍历元素的时候,可以考虑使用enumerate函数,enumerate函数接受一个可遍历的对象,如列表.字符串 比如我们有一个["one","two","there"]的列表,我们需要在列表的每个元素前面加上他的编号 复制代码 代码如下: i = 0seq = ["one","two","three&qu

  • Python递归求出列表(包括列表中的子列表)的最大值实例

    要求:求出列表中的所有值的最大数,包括列表中带有子列表的. 按照Python给出的内置函数(max)只能求出列表中的最大值,无法求出包括列表中的子列表的最大值 Python3代码如下: #!/usr/bin/env python3 # _*_ coding:UTF-8 _*_ list_tmp = [1,3,5,7,9,11] print(max(list_tmp)) 返回的结果为:11 按照Python3给出内置函数(max)的方法想要违和他的要求求出列表包括子列表的数,他就会给你进行报错.

随机推荐