欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++面试题之最小的K个数(topK问题) 题解

程序员文章站 2022-06-17 19:20:22
c++面试题之最小的k个数(topk问题) 题解 题目:输入n个整数,找出其中最小的k个数。例如:例如输入4 、5 、1、6、2、7、3 、8 这8 个数字,则最小的4 个数字是1 、2、3 、4...

c++面试题之最小的k个数(topk问题) 题解

题目:输入n个整数,找出其中最小的k个数。例如:例如输入4 、5 、1、6、2、7、3 、8 这8 个数字,则最小的4 个数字是1 、2、3 、4

分析:

想到3种方法,第1种是先快排,然后挑出其中的前k个,时间复杂度为o(n logn);第2种方法是使用partition函数(进行一次快速排序用哨兵数分割数组中的数据),时间复杂度:o(n);第3种是小顶堆(优先队列),时间复杂度:o(n logk). 第3种在海量计算中应用广泛...

stl中的优先队列默认是大顶堆,此题是生成一个小顶堆,即可解决...

堆排序

数据对象为:数组,链表,不稳定,时间复杂度为o(n logk),空间复杂度为o(1),(最大堆,有序区)从堆顶把根卸出来放在有序区之前,再恢复堆。

priority_queue调用 stl里面的 make_heap(), pop_heap(), push_heap() 算法实现,也算是堆的另外一种形式。

方法3 大顶二叉堆

ac代码:

#include<cstdio>

#include<vector>

#include<queue> // 用到其中的优先队列priority_queue

using namespace std;

class solution {

public:

vector<int> getleastnumbers_solution(vector<int> input, int k)

{

vector<int> res;

if(k<=0 || k>input.size()) return res;

priority_queue<int> q; // stl中的优先队列默认是大顶堆

unsigned int i=0;

while(i<input.size())

{

q.push(input[i]);

if(q.size()>k) q.pop();

i++;

}

while(!q.empty())

{

res.push_back(q.top()); // c语言中的top()可返回顶部元素的值,也可返回顶部元素的指针,程序员自行设计; c++的stl中top()返回的是顶部的值

q.pop();

}

return res;

}

};

// 以下为测试部分

int main()

{

solution sol;

vector<int> vec1={2,5,3,7,9,8,6};

vector<int> vec2={5,7,6,9,11,10,8};

vector<int> vec3={7,4,6,5};

vector<int> res1=sol.getleastnumbers_solution(vec1,3);

vector<int> res2=sol.getleastnumbers_solution(vec2,5);

vector<int> res3=sol.getleastnumbers_solution(vec3,2);

 
for(int i:res1)

printf("%d ", i);

printf("\n");

for(int i:res2)

printf("%d ", i);

printf("\n");

for(int i:res3)

printf("%d ", i);

printf("\n");

return 0;

}

priority_queue函数列表

函数

描述

构造析构

priority_queue c

创建一个空的queue 。
注:priority_queue构造函数有7个版本,请查阅msdn

数据访问与增减

c.top()

返回队列头部数据

c.push(elem)

在队列尾部增加elem数据

c.pop()

队列头部数据出队

其它操作

c.empty()

判断队列是否为空

c.size()

返回队列中数据的个数

 

可以看出priority_queue的函数列表与栈stack的函数列表是相同的。

方法2 partition函数

ac代码:

#include<cstdio>

#include<vector>

using namespace std;

class solution{

public:

int partion(vector<int> a,int len,int low,int high)

{

int base=a[low];

int i=low, j=high;

while(i != j)

{

while(i<j && a[j]>=base) j--;

while(i<j && a[i]<=base) i++;

if(i<j) // 交换

{

int temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

a[low]=a[i];

a[i]=base;

return i;

}

vector<int> getleastnumbers_solution(vector<int> input, int k)

{

vector<int> res;

int len=input.size();

if(len<=0) return res;

int start=0;

int end=len-1;

int index=partion(input,len,start,end);

while(k-1 != index)

{

if(k-1 < index)

{

end=index-1;

index=partion(input,len,start,end);

}

else

{

start=index+1;

index=partion(input,len,start,end);

}

}

for(int i=0;i<k;i++)

res.push_back(input[i]);

return res;

}

};

// 以下为测试部分

int main()

{

solution sol;

vector<int> vec1={2,5,3,7,9,8,6};

vector<int> vec2={5,7,6,9,11,10,8};

vector<int> vec3={7,4,6,5};

vector<int> res1=sol.getleastnumbers_solution(vec1,3);

vector<int> res2=sol.getleastnumbers_solution(vec2,5);

vector<int> res3=sol.getleastnumbers_solution(vec3,2);

 
for(int &i:res1)

printf("%d ", i);

printf("\n");

for(int &i:res2)

printf("%d ", i);

printf("\n");

for(int &i:res3)

printf("%d ", i);

printf("\n");

return 0;

}

其实还有一种思路:

可以用较为hack的手段进行。比如要获得一个堆中的最小值:

priority_queue<int> pq;

pq.push( -1 * v1) ;

pq.push( -1 * v2) ;

pq.push( -1 * v3) ;

分别是插入v1, v2, v3变量的相反数,那么取相反数后的这些值变相构成为了最大堆,只是每次从pq取值后,要再次乘以-1即可获得堆中最小值...