一步一步写算法（之寻找丢失的数）
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】
假设我们有一个1亿个数据，其中数据的范围是0~1亿，也就是100M的数据。但是这个数组中丢了一些数据，比如说少了5啊，少了10啊，那么有什么办法可以把这些丢失的数据找回来呢？这个题目不难，但是它可以帮助我们拓展思路，不断提高算法的运行效率。
对于这个问题，我们一个最简单的思路就是对各个数据进行flag判断，然后依次输出数据。
copy to clipboardprint?void get_lost_number(int data[], int length)
{
int index;
assert(NULL != data && 0 != length);
unsigned char* pFlag = (unsigned char*)malloc(length * sizeof(unsigned char));
memset(pFlag, 0, length * sizeof(unsigned char));
for(index = 0; index < length; index ++){
if(0 == pFlag[data[index]])
pFlag[data[index]] = 1;
}
for(index = 0; index < length; index++){
if(0 == pFlag[index])
printf("%d\n", index);
}
free(pFlag);
return;
}
void get_lost_number(int data[], int length)
{
int index;
assert(NULL != data && 0 != length);
unsigned char* pFlag = (unsigned char*)malloc(length * sizeof(unsigned char));
memset(pFlag, 0, length * sizeof(unsigned char));
for(index = 0; index < length; index ++){
if(0 == pFlag[data[index]])
pFlag[data[index]] = 1;
}
for(index = 0; index < length; index++){
if(0 == pFlag[index])
printf("%d\n", index);
}
free(pFlag);
return;
} 可能朋友也看到了，上面的代码需要分配和原来数据一样length的空间。其实我们可以用bit进行访问标志的设定，所以我们申请的空间还可以减少。
copy to clipboardprint?void get_lost_number(int data[], int length)
{
int index;
assert(NULL != data && 0 != length);
unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3);
memset(pFlag, 0, length * sizeof(unsigned char));
for(index = 0; index < length; index ++){
if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))
pFlag[data[index] >> 3] |= 1 << (data[index] % 8);
}
for(index = 0; index < length; index++){
if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))
printf("%d\n", index);
}
free(pFlag);
return;
}
void get_lost_number(int data[], int length)
{
int index;
assert(NULL != data && 0 != length);
unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3);
memset(pFlag, 0, length * sizeof(unsigned char));
for(index = 0; index < length; index ++){
if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))
pFlag[data[index] >> 3] |= 1 << (data[index] % 8);
}
for(index = 0; index < length; index++){
if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))
printf("%d\n", index);
}
free(pFlag);
return;
} 上面的代码已经在空间上面有所减小，那么有什么办法并行运算这些数据呢？
copy to clipboardprint?void get_lost_number(int data[], int length)
{
int index;
RANGE range[4] = {0};
assert(NULL != data && 0 != length);
unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3);
memset(pFlag, 0, length * sizeof(unsigned char));
range[0].start = 0, range[0].end = length >> 2;
range[1].start = length >> 2 , range[1].end = length >> 1;
range[2].start = length >> 1 , range[2].end = length >> 2 * 3;
range[3].start = length >> 2 * 3, range[3].end = length;
#pragma omp parallel for
for(index = 0; index < 4; index ++){
_get_lost_number(data, range[index].start, range[index].end, pFlag);
}
补充：软件开发 , C语言 ,
