问题描述

一个最多包含n个正整数的文件，每个数小于n，其中n为10000000。要求升序排列整数列表，最多使用1MB的内存，运行时间尽可能短。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>                                                                                                                                                              
#include <stdlib.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1 + N/BITSPERWORD] = {0};

/**
 * i>>SHIFT相当于i/32，用于确定i在第几个int数组中
 * 其中i&MASK含义为i%32，用于确定在int中的第几位
 */
void set(int i)
{
    a[i >> SHIFT] |= (1 << (i & MASK));
}

void clr(int i)
{
    a[i >> SHIFT] &= (0 << (i & MASK));
}

int test(int i)
{
    return a[i >> SHIFT] & (1 << (i & MASK));
}

int main(void)
{
    int i;
    while (scanf("%d", &i) != EOF)
    {
        set(i);
    }
    for (i=0; i<N; i++)
    {
        if (test(i))
        {
            printf("%d\n", i);
        }
    }
    return 0;
}

习题5

通过shell命令echo "scale=2; 10000000 / 1024 / 8 / 1024.0" | bc计算该程序运行时至少需要的存储空间为1.19MB，如果仅提供了1MB的存储空间，则需要更改上述程序的处理方式。

可采用多趟算法，多趟读入输入数据，每次完成一步。针对该题，可采用2步来完成，int数组的大小变更为5000000/8，比之前小了一半。第一步处理0-4999999之间的数据，第二步处理5000000-999999之间的数据。

习题6

如果是每个整数至少出现10次，而不是原先的一次。可以使用4bit来统计出现的次数，申请的数组大小变为了10000000/2。只要是每个整数有出现的最多次数上限该种处理方式就合适，当然整数出现的上限不能太大，否则该算法就没有了任何优势。

习题9

对一个大的数组的初始化操作需要耗费一些时间，为了消除数组的初始化，可以通过两个额外的数组来解决，这是典型的用空间换时间的方法。

      +---+---+---+---+---+---+---+----+
data  |   |   | 3 |   | 2 |   | 8 |    |
      +---+---+---+---+---+---+---+----+
                                        
      +---+---+---+---+---+---+---+----+
from  |   |   | 0 |   | 2 |   | 1 |    |
      +---+---+---+---+---+---+---+----+
                                        
      +---+---+---+---+---+---+---+----+
to    | 1 | 5 | 3 |   |   |   |   |    |
      +---+---+---+---+---+---+---+----+
                                        
                    ^                   
                    +                   
                   top

上图中data为要初始化的数组，from和to为辅助数组。如果data[i]已经初始化，则from[i]<top，to[from[i]]=i。from是一个简单的标识，to和top确保了from中不会写入内存中的随机内容。

习题11

该题的答案太他妈逗了，为了能够解决两地之间的数据传输瓶颈，作者给出的答案居然是用信鸽传输图片的底片后再将底片放大的方式来代替原先的用汽车运输的方式，这就是中国古代的飞鸽传书啊。

习题12

该题在《三傻大闹宝莱坞》中见过，这跟编程毛线关系也没有啊。