刘德华见龙卸甲:一步一步写算法（之寻找丢失的数）

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

假设我们有一个1亿个数据，其中数据的范围是0~1亿，也就是100M的数据。但是这个数组中丢了一些数据，比如说少了5啊，少了10啊，那么有什么办法可以把这些丢失的数据找回来呢？这个题目不难，但是它可以帮助我们拓展思路，不断提高算法的运行效率。

对于这个问题，我们一个最简单的思路就是对各个数据进行flag判断，然后依次输出数据。

view plaincopy to clipboardprint?

1. void get_lost_number(int data[], int length)
2. {
3. int index;
5. assert(NULL != data && 0 != length);
6. unsigned char* pFlag = (unsigned char*)malloc(length * sizeof(unsigned char));
7. memset(pFlag, 0, length * sizeof(unsigned char));
9. for(index = 0; index < length; index ++){
10. if(0 == pFlag[data[index]])
11. pFlag[data[index]] = 1;
12. }
14. for(index = 0; index < length; index++){
15. if(0 == pFlag[index])
16. printf("%d\n", index);
17. }
19. free(pFlag);
20. return;
21. }

view plaincopy to clipboardprint?

1. void get_lost_number(int data[], int length)
2. {
3. int index;
5. assert(NULL != data && 0 != length);
6. unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3);
7. memset(pFlag, 0, length * sizeof(unsigned char));
9. for(index = 0; index < length; index ++){
10. if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))
11. pFlag[data[index] >> 3] |= 1 << (data[index] % 8);
12. }
14. for(index = 0; index < length; index++){
15. if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))
16. printf("%d\n", index);
17. }
19. free(pFlag);
20. return;
21. }

1. void get_lost_number(int data[], int length)
2. {
3. int index;
4. RANGE range[4] = {0};
6. assert(NULL != data && 0 != length);
7. unsigned char* pFlag = (unsigned char*)malloc((length + 7) >> 3);
8. memset(pFlag, 0, length * sizeof(unsigned char));
10. range[0].start = 0, range[0].end = length >> 2;
11. range[1].start = length >> 2 , range[1].end = length >> 1;
12. range[2].start = length >> 1 , range[2].end = length >> 2 * 3;
13. range[3].start = length >> 2 * 3, range[3].end = length;
15. #pragma omp parallel for
16. for(index = 0; index < 4; index ++){
17. _get_lost_number(data, range[index].start, range[index].end, pFlag);
18. }
20. for(index = 0; index < length; index++){
21. if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))
22. printf("%d\n", index);
23. }
25. free(pFlag);
26. return;
27. }

view plaincopy to clipboardprint?

1. typedef struct _RANGE
2. {
3. int start;
4. int end;
5. }RANGE;
7. void _get_lost_number(int data[], int start, int end, unsigned char pFlag[])
8. {
9. int index;
11. for(index = start; index < end; index++){
12. if(0 == (pFlag[data[index] >> 3] & (1 << (data[index] % 8))))
13. pFlag[data[index] >> 3] |= 1 << (data[index] % 8);
14. }
15. }

（1）代码的优化是可以不断进行得，但是不见得适用于所有的场景

（2）目前的cpu已经开始从2核->4核->8核转变，朋友们在可能的情况下尽量多掌握一些多核编程的知识。