小乐乐与序列

[编程题]小乐乐与序列

热度指数：19715 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

老师给了小乐乐一个正整数序列，要求小乐乐把这个序列去重后按从小到大排序。但是老师给出的序列太长了，小乐乐没办法耐心的去重并排序，请你帮助他。

输入描述:

第一行包含一个正整数n，表示老师给出的序列有n个数。接下来有n行，每行一个正整数k，为序列中每一个元素的值。(1 ≤ n ≤ 10⁵，1 ≤ k ≤ n)

输出描述:

输出一行，为去重排序后的序列，每个数后面有一个空格。

示例1

输入

输出

1 2

示例2

输入

输出

1 2 3 4 5

算法知识视频讲解

徐文达

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

void QuickSort(int* left, int* right)
{
    assert(left && right);

    //只剩1个元素，无需继续排序
    //开始回归
    if (left >= right)
    {
        return;
    }

    int* i = left;
    int* j = right;
    int pivot = *left;

    while (i < j)
    {
        //j在小于pivot的地方停下来
        while (*j >= pivot && j > i)
        {
            j--;
        }
        *i = *j;

        //i在大于pivot的地方停下来
        while (*i <= pivot && i < j)
        {
            i++;
        }
        *j = *i;
    }
    //将基准元素pivot放入它该在的位置
    *j = pivot;

    QuickSort(left, i - 1);//i是上一轮已经处理好的元素，所以 -1 处理左边的元素
    QuickSort(j + 1, right);//j是上一轮已经处理好的元素，所以 +1 处理右边的元素
}

int main()
{
    int n = 0;
    int i = 0;
    int* p = NULL;

    scanf("%d", &n);

    //开辟空间
    p = (int*)malloc(sizeof(int) * n);
    if (!p)
    {
        perror("malloc:p");
        return 1;
    }

    //录入数列
    for (i = 0; i < n; i++)
    {
        scanf("%d", p + i);
    }

    //进行排序
    QuickSort(p, p + n - 1);

    //进行去重输出
    printf("%d ", *p);
    for (i = 1; i < n; i++)
    {
        if (*(p + i) == *(p + i - 1))
        {
            continue;
        }
        printf("%d ", *(p + i));
    }

    //释放空间
    free(p);
    p = NULL;

    return 0;
}

编辑于 2024-03-20 18:58:19 回复(0)

诗奕

#include <stdio.h>

int main() {
    int n=0;
    int tmp=0;
    int arr[100001]={0};
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&tmp);
        arr[tmp]=tmp;
    }
    for(int i=0;i<100001;i++){
        if(arr[i]!=0){
            printf("%d ",arr[i]);
        }
    }
    return 0;
}

编辑于 2024-02-04 16:53:53 回复(1)

牛客575029355号

#include<stdio.h>
int main()
{
    int arr[100000]= {0};
    int n = 0;
    scanf("%d",&n);
    int i = 0;
    int k = 0; //每一行的正整数
    for(i = 0;i<n;i++)
    {
        scanf("%d",&k);
        arr[k] = k;
    }
    for(i = 0;i<n;i++) //打印
    {
        if(arr[i])//不为0的时候打印
            printf("%d ",arr[i]);
    }
    return 0;
}

发表于 2022-05-16 16:17:58 回复(0)

阿金要努力

#include <stdio.h>
int main()
{
    int n = 0;
    int arr[100000] = {0};
    int i = 0;
    int tmp = 0;
    scanf("%d", &n);
    for(i=0; i<n; i++)
   {
        scanf("%d", &tmp);
        arr[tmp] = tmp;
   }
    for(i=0;i<n;i++)
    {
        if(arr[i]!=0)
            printf("%d ",arr[i]);
    }
    return 0;
}

发表于 2022-01-03 16:45:41 回复(1)

TRistbl

#include<stdio.h>
int main()
{
    int i, n, k;
    while (~scanf("%d", &n))
    {
        int arr[100001] = { 0 };
        int max = 0;

        //出现过的数字，该元素改为1，作为标记
        for (i = 0; i < n; i++)
        {
            scanf("%d", &k);
            arr[k] = 1;
            if (max < k)
                max = k;
        }

        //正序输出标记过的数
        for (i = 0; i <= max; i++)
        {
            if (arr[i])
                printf("%d ", i);
        }
        printf("\n");
    }
    return 0;
}

发表于 2021-12-02 02:02:39 回复(0)

XHNC

8/10用例不能通过，可以帮我看看哪里出了问题吗？

#include<stdio.h>
#include<malloc.h>
int cmp(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
}
int main()
{
    int n,i,j;
    scanf("%d",&n);
    int* arr = (int*)malloc(n * sizeof(int));
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    for(i=0;i<n;i++)
    {
       for(j=i+1;j<n;j++)
       {
           if(arr[j]==arr[i])//相同则置零
               arr[j]=0;
       }
    }
    qsort(arr,n,sizeof(int),cmp);//数据排序
   for(i=0;i<n;i++)
   {
      if(arr[i]!=0)
      {
          printf("%d ",arr[i]);
      }
   }
    return 0;
}

发表于 2021-08-23 11:17:07 回复(6)