九八寒露——HRBUST OJ 1164 数字去重和排序

HRBUST OJ 1164 数字去重和排序

VJ传送门

https://vjudge.net/problem/HRBUST-1164

HRBUST OJ传送门

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1164

Time Limit: 5000 MS Memory Limit: 65536 K

Description

用计算机随机生成了N个0到910305（包含0和910305）之间的随机整数（N≤100000000），对于其中重复的数字，只保留一个，把其余相同的数去掉。然后再把这些数从小到大排序。

请你完成“去重”与“排序”的工作。

Input

输入有2行，第1行为1个正整数，表示所生成的随机数的个数：

N

第2行有N个用空格隔开的正整数，为所产生的随机数。

Output

输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

Sample Input

10

20 40 32 67 40 20 89 300 400 15

Sample Output

8

15 20 32 40 67 89 300 400

Hint

推荐使用scanf  printf

输入数据有多组！

Author

黄李龙

————————————————————————————————————————

Answer

这题因为数据范围不大，所以很容易想到用“桶排序”（计数排序）来做，但是小心哦！

Problem

如果你在main函数里写 int s[910306]; 的话，编译可以通过，但是运行就不行了！

int main()
{
    int s[910306];
           

是真的吗?

事实的真相到底是什么呢？实验让你眼见为实，有请codeblocks~（咳咳，我错了，这里不是《是真的吗》的节目现场）

这是为什么呢?我后来查找了一些资料。

原来，一个源程序编译运行所占用的内存分配有五大分区：

代码区，常量区，全局区（静态区），堆区，栈区

而各个分区的内存分配大小限制是不同的。如果将数组定义在main函数内，那么作为局部变量，它的内存由栈区分配，而栈区的内存默认大小一般是1M或2M，1M=1024K=1048576B（字节），1个int占4字节，1048576 / 4 == 262144，2*1048576 / 4 == 524288，所以理论上最多可以定义略小于26万或52万位的int数组，而题目所需的91万就不够了。如果定义91万位，那么就会“栈溢出”（STACK_OVERFLOW）

那怎么办？

有3种办法：

1    把后台系统的栈区内存分配大小设置更改变大

不行！我们这是要向VJ、OJ提交代码，难道把VJ、OJ给黑掉然后更改设置？臣妾做不到啊！不行！！！

2    把int数组改成bool数组

1个bool占1字节，1048576 / 1 == 1048576，2*1048576 / 1 == 2097152，也就是说可以在main函数中定义略小于104万或209万的bool数组呢！91万够了！不过，改成了bool数组，我们就只能知道一个数是否存在，而无法统计这个数存在几次了，如果一定要知道，怎么办？

int main()
{
    bool s[910306];
           

3    把数组定义在main函数外

如果将数组定义在main函数外，那么作为全局变量，它的内存由全局区（静态区）分配，而全局区（静态区）的内存默认大小一般是2G。天哪，是栈区的1024倍！50万 * 1000等于5亿（5e8）位！够了，够了，别说是91万，9100万都够了！Exciting！但是！还是要看题目的限制，Memory Limit: 65536 K，65536 * 1024 / 4 == 16777216，1677万，91万够了，可以！别傻傻地真的定义9100万了，浪费内存空间不说，题目还不允许！

int s[910306];
int main()
{
           

补充    改成堆（动态内存分配）

堆区的内存大小默认没有软限制，只有硬限制，理论上是硬盘大小。不过进程的虚拟内存大小由机器字长确定，如32位机的进程虚拟地址空间为2的32次方即4G，比全局区（静态区）又大一倍。但是同样地，还是要看题目的限制，Memory Limit是多少，不能超出。有兴趣的小伙伴可以自己研究一下《数据结构》课程的相关知识，这里不再详述。

AC代码（C++）

3    把数组定义在main函数外

#include<stdio.h>
#include<string.h>
int s[910306];
int main()
{
    int n,x,z;
    while(~scanf("%d",&n))
    {
        memset(s,0,sizeof(s));
        z=0;
        while(n--)
        {
            scanf("%d",&x);
            if(!s[x]) z++;
            s[x]++;
        }
        printf("%d\n",z);
        z=0;
        for(int i=0;i<910306;i++)
        {
            if(s[i])
            {
                if(z++) printf(" ");
                printf("%d",i);
            }
        }
        printf("\n");
    }
    return 0;
}
           

2    把int数组改成bool数组

#include<stdio.h>
#include<string.h>
int main()
{
    bool s[910306];
    int n,x,z;
    while(~scanf("%d",&n))
    {
        memset(s,false,sizeof(s));
        z=0;
        while(n--)
        {
            scanf("%d",&x);
            if(!s[x]) z++;
            s[x]=true;
        }
        printf("%d\n",z);
        z=0;
        for(int i=0;i<910306;i++)
        {
            if(s[i])
            {
                if(z++) printf(" ");
                printf("%d",i);
            }
        }
        printf("\n");
    }
    return 0;
}
           

2+3    把int数组改成bool数组+把数组定义在main函数外

#include<stdio.h>
#include<string.h>
bool s[910306];
int main()
{
    int n,x,z;
    while(~scanf("%d",&n))
    {
        memset(s,false,sizeof(s));
        z=0;
        while(n--)
        {
            scanf("%d",&x);
            if(!s[x]) z++;
            s[x]=true;
        }
        printf("%d\n",z);
        z=0;
        for(int i=0;i<910306;i++)
        {
            if(s[i])
            {
                if(z++) printf(" ");
                printf("%d",i);
            }
        }
        printf("\n");
    }
    return 0;
}
           

3个代码提交结果

   Result        Time        Mem        Length

                     (ms)         (MB)

Accepted       439             4             525

Accepted       438           1.3            537

Accepted       429           1.3            533

可以看出2+3是最好的选择，时间最少，内存也小。

那如果改成堆的话时间会更少还是更多呢？

这个问题就留给小伙伴们自己去寻找答案啦~