5.查找最小的k个元素(数组)

题目： 输入n个整数，输出其中最小的k个，例如输入1,2,3,4,5,6,7,8这8个数，则最小的4个是1,2,3,4(输出不要求有序)

解： 利用快速排序的partition，算导上求第k大数的思想，求出第k大的数，然后遍历数组，如果a[i]<a[k]，那么a[i]就是前k小的元素之一。 求第k大的元素时间是o(n)，求前k小元素时间是o(n),所以总时间是o(n)

代码：

/*

     求数组最小的k个数，参考算法导论求中位数的k个临近值，首先求出第k小的数，然后o(n)遍历，若<，则是前k小的数之一

 */

#include<iostream>

#include<time.h>

#include<cstdlib>

using namespace std;

// a[begin]->a[end]

int partition(int *a,int begin,int end)

{

    srand((int)time(NULL));

    int pivot=rand()%(end-begin+)+begin;

    int temp;

    if(pivot!=end)

    {

        temp=a[pivot];

        a[pivot]=a[end];

        a[end]=temp;

    }

    int i=begin-,j=begin;

    int x=a[end];

    for(j=begin;j<end;j++)

    {

        if(a[j]<=x)

        {

            i++;

            temp=a[i];

            a[i]=a[j];

            a[j]=temp;

        }

    }

    temp=a[i+];

    a[i+]=a[end];

    a[end]=temp;

    //i+1是在a整个数组中的下标，并不是相对于a[begin,end]的下标

    return i+;

}

//第k大的元素应该是k-1位置

//a[p]---a[r]

void findk(int *a,int p,int r,int k)

{

    int i,j,q;

    i=p;j=r;

    q=partition(a,p,r);

    while((k-)!=q)

    {

        if((k-)<q)

            j=q-;

        else

            i=q+;

        q=partition(a,i,j);

    }

    //a[q]就是第k大的数，现在在k-1位置,[0,k-1]就是前k小的数

    cout<<"最小的"<<k<<"个数是: ";

    for(int s=p;s<=q;s++)

        cout<<a[s]<<" ";

    cout<<endl;

}

int main(void)

{

    /*以随机生成的8个数为例*/

    //int a[8]={1,3,2,4,6,7,5,8};

    int a[]={};

    int k,i;

    srand((int)time(NULL));

    for(i=;i<;i++)

        a[i]=rand()%;

    cout<<"原数组是: ";

    for(i=;i<;i++)

        cout<<a[i]<<"  ";

    cout<<endl;

    cout<<"输入k: ";

    cin>>k;

    findk(a,,,k);

    return ;

}