面试题30.最小的k个数

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

这道题是典型的TopK问题,剑指Offer提供了两种方法来实现,一种方法是parition方法,一种

方法是建立一个大小为k的堆进行topk求解

这里我们只解释第一种方法:

1.首先随机查找数组中一个元素作为一个基准,然后parition一次使得数组左边的元素小于基本,数组右边的元素大于基准。

2.此时将再将基准插入到数组适当的位置并返回该位置的索引。

3.如果索引index小于k-1则继续在[index+1,end]范围内进行parition,

4.如果索引index大于k-1则继续在[start,index-1]范围内进行pariton

5.直到index==k-1时候结束

代码实现如下:

 #include <iostream>
using namespace std; int Partiton(int array[],int start,int end)
{
int i=start;
int j=end;
int k=;
int base=array[];
while(i<j)
{
if(i<j&&base<=array[j])
j--; if(i<j)
{
array[i]=array[j];
i++;
} if(i<j&&base>array[i])
i++; if(i<j)
{
array[j]=array[i];
j--;
}
} array[i]=base; return i;
} int FindTopK(int array[],int start,int end,int k)
{
int startindex=start;
int endindex=end;
int index=Partiton(array,startindex,endindex); while(index!=k-)
{
if(index>k-)
{
endindex=index-;
index=Partiton(array,startindex,endindex);
}
else
{
startindex=index+;
index=Partiton(array,startindex,endindex);
}
}
return index;
} int main()
{
int array[]={,,,,,,,};
int len=;
int Index;
int k=;
Index=FindTopK(array,,len-,k); cout<<"The Top K number is: ";
for(int i=;i<Index+;i++)
{
cout<<array[i]<<" ";
}
cout<<endl;
system("pause");
return ;
}

运行截图:

面试题30.最小的k个数

上一篇:全流程指导Visual Studio Code+Markdown Nice+gitee+PicGo管理自己的技术博客文章


下一篇:Nginx错误日志