题解 | #明明的随机数#

#include <stdio.h>
#include <stdlib.h>

//快排 的算法
void quick_sort(int arry[],int low,int high)
{
    if(low>=high)
        return;
    int key=arry[low];
    int i=low;
    int j=high;
    while(i<j)
    {
        while(i<j && arry[j]>=key)
            j--;
        if(i<j)
        {
            arry[i]=arry[j];
            i++;
        }
        while(i<j && arry[i]<=key)
            i++;
        if(i<j)
        {
            arry[j]=arry[i];
            j--;
        }
    }
    arry[i]=key;
    
    quick_sort(arry, low, i-1);
    quick_sort(arry, i+1, high);
}

//无序去重的方法
//一点点区别是思路是发现重复的把这个重复的和最后面的去对调
//比数组顺序移动要快不少
int repeat_remove(int arry[],int len)
{
    int low = 1, high = len - 1;
    while (low <=high)//注意考虑等号的情况
    {
        for (int i = 0; i < low; i++)
        {
            if (arry[i] == arry[low])
            {
                int var = arry[high];
                arry[high] = arry[low];
                arry[low] = var;
                high--;//尾值向前移一位
                low--;//保证low不变
                break;
            }
        }
        low++;
    }
    return high+1; //不能是low+1 因为low最后会比high大
}

//有序数组的去重方法
//原理就是找数组相邻的数据
//然后数组集体前移N位
int order_repeat_remove(int arry[],int len)
{
    int max = arry[len - 1];
    for (int i = 0;i < len;i++)
    {
        int j = i + 1;
        while (arry[i]==arry[j])
        {
            j++;
        }
        if (j > i + 1)
        {
            int removenum = j - i - 1;
            for (int kk = j; kk < len; kk++)
            {
                arry[kk - removenum] = arry[kk];
                arry[kk] = max + 1;//目的在于保证这个数据和其他所有数据都不一样
            }
            len = len - removenum;
        }
    }
    return len;
}

void dispaly(int arry[],int len)
{
    for(int i=0;i<len;i++)
    {
        printf("%d\n",arry[i]);
    }
}

int main()
{
    int count,number;
    scanf("%d",&count);
    int * array=(int *)(malloc(count*sizeof(int)));
    int i=0;
    while(scanf("%d",&number)!=EOF)//构建输入数组
    {
        array[i]=number;
        i++;
    }
    int len=repeat_remove(array,count);//先去重在排序
    quick_sort(array,0,len-1);   
   // quick_sort(array,0,count-1); //先排序在去重
   // int len=order_repeat_remove(array,count);
        dispaly(array,len);
}