Manchester- 【明明的随机数】（合并排序实现）

解题思路:
1.把输入的随机数进行排序；（这里用的是合并排序）实现如下，具体遇到大数据排序再讲，复制用就行。

void Mesort(int *A,int *B,int left,int right);
/*A[]为待排序数组，B[],用于存过度值，left赋值为0，right赋值为A[]最后一个元素下标即可；
排好序的结果自然就在A[]里面；*/
void Merge(int *A,int *B,int left,int middle,int right);
void copy(int *A,int *B,int left,int right);

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];
}

2.移除相同随机数即：把A[]中元素赋值到C[]里面，相同的元素不赋值；（移除前提排好序）

int yichu(int *A,int *C,int N)
{
      int n= N;  //n用于存放C[]中元素个数，输出结果使用
      C[0]=A[0];  //先把A[]第一个元素赋值
  for(int i=1,j=1;i<N;i++)   //A[]，中元素下标从1开始，与前一个相同则不复制到C[];
    {
       if(A[i]==A[i-1])
                n--;   //遇到相同的随机数，减去1,不赋值
                else   //不相同则赋值到C[]里面
                {C[j]=A[i];j++;} //不相同则赋值到C[]里面,同时C[],元素下标加1
    }

return n;    //把n返回，用于输出
}

参考代码:

#include <stdio.h>
#include <malloc.h>
void function( int *A, int N );

int yichu( int *A, int *C, int N );

void input( int *A, int N );

void output( int *C, int N );

/*--------------------------------------------------*/
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 );


/*------------------------------------------------*/
int main()
{
    int    N;
    int    *A;

    while ( scanf( "%d", &N ) != EOF )
    {
        A = (int *) malloc( N * sizeof(int) );
        function( A, N );
    }
    return(0);
}


/*------------------------------------------------*/

void function( int *A, int N )
{
    int    *C    = (int *) malloc( N * sizeof(int) );  //C[]用于存移除相同元素后的随机数
    int    *B    = (int *) malloc( N * sizeof(int) );   //排序过程使用

    input( A, N );     //输入随机数
             Mesort( A, B, 0, N - 1 );   //排序
                   N = yichu( A, C, N );    //移除相同随机数，并把结果存于C[]
                             output( C, N );       //输出结果

    return;
}


/*------------------------------------------------*/
int yichu( int *A, int *C, int N )
{
    int n = N;
    C[0] = A[0];
    for ( int i = 1, j = 1; i < N; i++ )
    {
        if ( A[i] == A[i - 1] )
            n--;
               else{ C[j] = A[i]; j++; }
    }

    return(n);
}


/*------------------------------------------------*/
void output( int *C, int N )
{
    printf( "%d\n", N );     //输出元素个数，带换行符
       for ( int i = 0; i < N - 1; i++ )
            printf( "%d ", C[i] );     //输出前面N-1个元素，带空格
                printf( "%d\n", C[N - 1] );    //输出第N个元素，不带空格，加换行符
}


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


/*==================================================================*/
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];
}

别忘点赞哦-.-