[练习题] 找出1-100中缺失的两个数

现有1~100共一百个数, 已乱序放入一个有98个元素的数组num[98]. 要求设计一个尽量简单的方案, 找出1~100中缺失的两个数, 输出这两个数. 注意: 程序不需要实现自然数随机放入数组的过程.

挣扎了半天没想到什么好办法，只想到了两个几乎一样的土方法。

第一种方法：开一个100大小的数组，然后把当前的98个数字都放进新的数组，然后扫一遍就能知道哪两个数字缺失了。

#include<iostream>
using namespace std;

int num[98];

void init()
{
    // 题目说是乱序, 不过不管什么顺序都不影响程序,
    // 所以为了方便, 以如下的方式初始化
    int idx = 0;
    for(int i = 1; i <= 100; i++)
    {
        if(i == 14 || i == 57)
            continue;
        num[idx++] = i;
    }
}

void find()
{
    int cc[100];
    memset(cc, 0, sizeof(cc));

    for(int i = 0; i < 98; i++)
        cc[num[i]-1] = 1;
    for(int i = 0; i < 100; i++)
    {
        if(cc[i] == 0)
            printf("%d\n", i+1);
    }
}

int main()
{
    init();
    find();
    getchar();
    return 0;
}

第二种方法是利用C++ STL中的bitset来减少空间，有人可能会认为，把上述代码中的int cc[100]改成bool cc[100]也能减少空间，对的，但是减少的并不彻底，依旧有浪费。

一个int为4字节，一个bool为1字节，而bitset中的每一个位置只占用了1个位的空间。

所以空间占用情况如下：

int cc[100] -> 32bit * 100 = 3200bit

bool cc[100] -> 8bit * 100 = 800bit

bitset<100> -> 1bit * 100 = 100bit

#include<iostream>
#include<bitset>
using namespace std;

int num[98];

void init()
{
    // 题目说是乱序, 不过不管什么顺序都不影响程序,
    // 所以为了方便, 以如下的方式初始化
    int idx = 0;
    for(int i = 1; i <= 100; i++)
    {
        if(i == 14 || i == 57)
            continue;
        num[idx++] = i;
    }
}

void find()
{
    bitset<100> bitmap;
    bitmap.reset();

    for(int i = 0; i < 98; i++)
        bitmap.set(num[i]-1, true);

    for(int i = 0; i < 100; i++)
    {
        if(bitmap[i] == false)
            printf("%d\n", i+1);
    }
}

int main()
{
    init();
    find();
    getchar();
    return 0;
}

还可以充分利用int的每一位，模拟bitset的存储，有兴趣的可以写写看，也算是一种小小的巩固复习吧。

#include<iostream>
#include<cmath>

using namespace std;

int num[98];

void init()
{
	// 题目说是乱序, 不过不管什么顺序都不影响程序,
	// 所以为了方便, 以如下的方式初始化
	int idx = 0;
	for(int i = 1; i <= 100; i++)
	{
		if(i == 14 || i == 57)
			continue;
		num[idx++] = i;
	}
}

void find()
{
	int size = ceil(100.0/8);
	int cc[size];
	memset(cc, 0, sizeof(cc));

	for(int i = 0; i < 98; i++)
	{
		int x = (num[i]-1) / 8;
		int y = (num[i]-1) % 8;
		cc[x] |= 1 << y;
	}
	for(int i = 0; i < 100; i++)
	{
		int x = i / 8;
		int y = i % 8;
		if(!(cc[x] & (1<<y)))
			printf("%d\n", i+1);
	}
}

int main()
{
	init();
	find();
	getchar();
	return 0;
}

百度了一下基本上也就是这种方法了，甚至还有人说求出这98个数的和与积，也太不靠谱了吧。。。

总觉得还应该有更好的方法-_-#，不管有没有，反正本弱是没想出来，就留给学弟学妹们来解决吧。