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

#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(cinnk)
 {
  memset(a,0,sizeof(a));
  memset(re,0,sizeof(re));
  memset(vis,0,sizeof(vis));
  for(int i=0;i<n;i++)
  {
   cina[i];
  }
  dfs(0,0);
 }
 return 0;
}

#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(cinnk)
 {
  memset(a,0,sizeof(a));
  memset(re,0,sizeof(re));
  memset(vis,0,sizeof(vis));
  for(int i=0;i<n;i++)
  {
   cina[i];
  }
  dfs(0,0,0);
 }
 return 0;
}

#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(cinnk)
 {
  memset(a,0,sizeof(a));
  memset(re,0,sizeof(re));
  memset(vis,0,sizeof(vis));
  for(int i=0;i<n;i++)
  {
   cina[i];
  }
  dfs(0,1,0);
 }
 return 0;
}