Manchester- 查找最小的k个元素

解题思路:
①：输入n，k

②：输入n个数

③：使用合并排序把序列从小到大排序

④：输出下标为0到k-1的数

注意事项:

即便最小的k个数中有重复的也要输出，不能重复的只输出一遍

如输入 n=8 k=4     1 1 2 2 3 3 4 4

输出为1 1 2 2  不能是1 2 3 4

也就是输出函数不可以这样写(输出最小的k个不重复的数)

void out_put(int *A,int n,int k)
{
    int Counter=0,i=0;
     while(Counter!=k-1&&i<n)
      {
        if(A[i]!=A[i+1])
         {printf("%d ",A[i]);i++;Counter++;}
          else
           if(A[i]==A[i+1])
            i++;
      }/*输出前k-1个最小的数*/

      while(Counter!=k&&i<n)
       {
          if(A[i]!=A[i+1])
         {printf("%d\n",A[i]);i++;Counter++;}
          else
           if(A[i]==A[i+1])
            i++;
       }/*输出第k个最小的数*/

}

参考代码:

#include <stdio.h>
#include <malloc.h>

void Mesort( int *A, int *B, int left, int right );

void Merge( int *A, int *B, int left, int middle, int right );

void copy( int *A, int *B, int left, int right );


/*以上为合并排序函数声明*/
void in_put( int *A, int n );           /*输入数据*/
/* void out_put(int *A,int n,int k);/ *输出最小的k个不重复数字* / */
void Out_put( int *A, int n, int k );   /*输出最小的k个数字*/


int main()
{
    int    *A, *B;
    int    n, k;
    while ( scanf( "%d%d", &n, &k ) != EOF )
    {
        A    = (int *) malloc( n * sizeof(int) );    /*开辟空间*/
        B    = (int *) malloc( n * sizeof(int) );    /*合并排序中合并过程使用*/
        in_put( A, n );                                 /*输入数据*/
        Mesort( A, B, 0, n - 1 );                       /*合并排序*/
        Out_put( A, n, k );                             /*输出最小的k个数*/
    }
    return(0);
}


/*--------------------------------------------------------*/
void Mesort( int *A, int *B, int left, int right )
{
    if ( left < right )
    {
        int i = (left + right) / 2;
        Mesort( A, B, left, i );
        Mesort( A, B, i + 1, right );
        Merge( A, B, left, i, right );
        copy( A, B, left, right );
    }
}


/*--------------------------------------------------------*/
void Merge( int *A, int *B, int left, int middle, int right )
{
    int i = left, j = middle + 1, k = left;

    while ( (i <= middle) && (j <= right) )
    {
        if ( A[i] <= A[j] )
            B[k++] = A[i++];
        else
            B[k++] = A[j++];
    }

    if ( i > middle )
        for ( int q = j; q <= right; q++ )
            B[k++] = A[q];
    else
        for ( int q = i; q <= middle; q++ )
            B[k++] = A[q];
}


/*--------------------------------------------------------*/
void copy( int *A, int *B, int left, int right )
{
    for (; left <= right; left++ )
        A[left] = B[left];
}


/*--------------------------------------------------------*/
void in_put( int *A, int n )
{
    for ( int i = 0; i < n; i++ )
        scanf( "%d", &A[i] );
}


/*--------------------------------------------------------*/
void out_put( int *A, int n, int k )
{
    int Counter = 0, i = 0;
    while ( Counter != k - 1 && i < n )
    {
        if ( A[i] != A[i + 1] )
        {
            printf( "%d ", A[i] ); i++; Counter++;
        }else
        if ( A[i] == A[i + 1] )
            i++;
    } /*输出前k-1个最小的数*/

    while ( Counter != k && i < n )
    {
        if ( A[i] != A[i + 1] )
        {
            printf( "%d\n", A[i] ); i++; Counter++;
        }else
        if ( A[i] == A[i + 1] )
            i++;
    } /*输出第k个最小的数*/
}


void Out_put( int *A, int n, int k )
{
    if ( k <= n )
    {
        for ( int i = 0; i < k - 1; i++ )
            printf( "%d ", A[i] );
        printf( "%d\n", A[k - 1] );
    }
}

别忘点赞哦-.-