第 2 章第 2 题找“ 重数/漏数 ”问题二分法实现

问题分析

　　输入：一个包含了4 300 000 000个32位整数的文件( 已排序其中可能有重复出现的数字 )

　　输出：一个在这个文件中重复出现过了的数字

　　约束：内存消耗应尽量小

解答思路

　　分析题目，可以得知：

　　1. 32位整数最多能包含4294967296个整数 < 目标文件中整数的个数( 43亿 )，因此可知必然存在重复的数字。

　　2. 我们只需要找出一个重复出现过的整数即可。

　　我们可以首先将文件拆分为两个部分，一个部分包含区间 [0 - 2150000000) 的数，另一部分包含区间 [2150000000 - 4300000000) 的数。那么这两个区间必然有一个区间中存在的数的个数多于2150000000。然后，我们可以接着分下去。假设是区间 [0 - 2150000000) 中有大于2150000000个数字，那么它的子区间[0 - 1075000000) 和 [1075000000 - 215000) 中必然也有一个其中的数的个数多于1075000000。如此继续拆分区间直到找出一个只有一个元素的区间为止 - 它就是我们要找的那个整数。

效率分析

　　空间：主要占用的是磁盘空间，对内存空间需求很小。

　　时间：T(n) = T(n/2) + n，故时间复杂度为 O(log₂N)。N为输入文件中整数的个数。但要注意：处理的对象是磁盘文件，故不要对时间效率有什么期望。

代码实现

　　说明：为了方便测试，下面代码只用于查找一个包含10个以上整数的文件( 且每个数都小于等于9 )。如果需要换成正式版代码，请将宏N预设为2150000000，min初始化为0，max初始化为4299999999( 详见代码的注释部分 )：

  1 #include <iostream>
  2 #include <fstream>
  3 #include <string>
  4 
  5 using namespace std;
  6 
  7 // 正式版修改: N改为2150000000
  8 #define N 4 
  9 
 10 /*
 11  * 该函数将文件流io对应文件覆盖拷贝到文件流iot所对应文件
 12  * 最后再重置文件流
 13 */
 14 void copyfile(fstream &io, fstream &iot, int t)
 15 {
 16     int num;
 17     string filename = "data";
 18     string temfile1 = "1";
 19     string temfile2 = "2";
 20 
 21     io.close();
 22     io.clear();
 23     io.open(filename.c_str(), ofstream::out | ofstream::trunc);
 24     iot.close();
 25     iot.clear();
 26     if (t == 1) {
 27         iot.open(temfile1.c_str());
 28     }
 29     if (t == 2) {
 30         iot.open(temfile2.c_str());
 31     }
 32 
 33     while (iot >> num) {
 34         io << num;
 35         io << " ";
 36     }
 37 
 38     io.close();
 39     io.clear();
 40     io.open(filename.c_str());
 41     iot.close();
 42     iot.clear();
 43     if (t == 1) iot.open(temfile1.c_str(), ofstream::out | ofstream::trunc);
 44     if (t == 2) iot.open(temfile2.c_str(), ofstream::out | ofstream::trunc);
 45 }
 46 
 47 int main()
 48 {
 49     fstream io, io1, io2;
 50     
 51     /*
 52      * 打开三个文件，data是数据文件，1和2是两个空文件用来暂存数据。
 53     */
 54     string filename = "data";    
 55     string temfile1 = "1";
 56     string temfile2 = "2";
 57     io.open(filename.c_str());
 58     if (!io) return 1;
 59     io1.open(temfile1.c_str(), ofstream::out);
 60     if (!io1) return 1;
 61     io2.open(temfile2.c_str(), ofstream::out);
 62     if (!io2) return 1;
 63 
 64     // 正式版修改: n = 2150000000, max = 4299999999, min = 0。
 65     long long n = 4, num, max = 9, min = 0;
 66     long long p=0, q=0;
 67     int tag = 0;
 68 
 69     while (1) {
 70         p=0; q=0;
 71         /*
 72          * 将文件分为两部分，小于等于n的数存放进文件1，大于n的存放进文件2。
 73         */
 74         while (io >> num) {
 75             if (num <= n) {
 76                 p++;
 77                 io1 << num;
 78                 io1 << " ";
 79             }
 80             else if (num > n) {
 81                 q++;
 82                 io2 << num;
 83                 io2 << " ";
 84             }
 85         }
 86     
 87         /*
 88          * 将下一次循环要处理的数据转移到data中去
 89         */
 90         if (p > (n-min+1) ) {
 91             copyfile(io, io1, 1);
 92             max = n;
 93             n = (min + max)/2;
 94         }
 95         else if ( q > (max-n) ) { 
 96             copyfile(io, io2, 2);    
 97             min = n;
 98             n = (min + max)/2;
 99         }
100 
101         if (p ==0) {
102             io2 >> num;
103             cout << "Find: " << num << endl;
104             return 0;
105         }
106         if (q == 0) {
107             io1 >> num;
108             cout << "Find: " << num << endl;
109             return 0;
110         }
111 
112         /*
113          * 当最后分到的区间只有两个单位长度：
114          * 我通过设定标记，让数据再分最后一次后，data文件中的数据必然就是搜索到的结果。输出结果即可。
115         */
116         if (max == (min +1)) {
117             tag++;
118             if (tag != 2) continue;
119             io >> num;
120             cout << "Find: " << num << endl;
121             io.close();
122             return 0;
123         }        
124 
125         /*
126          * 重置两个暂存文件的文件流
127         */
128         io1.close();
129         io1.clear();
130         io1.open(temfile1.c_str(), ofstream::out);
131         io2.close();
132         io2.clear();
133         io2.open(temfile2.c_str(), ofstream::out);
134     }
135 
136     return 0;
137 }

运行测试

　　1. 先建立好三个文件：

　　2. 其中1和2是两个空文件，只是用来暂时存放数据的，而data存放我们需要处理的数据，其内容如下( 测试版程序 )：

　　3. 编译源代码并运行：

说明

　　1. 该程序要反复对上GB甚至十几GB的文件进行IO操作，故程序时间效率不高。另一方面想，需要处理的数据如此庞大，而所用内存只几百KB，自然要付出很大的时间代价。

　　2. 程序代码有些复杂，虽然我测试的几组数据都正确运行了，但也许还有漏洞，恳请读者指正。

第 2 章 第 2 题 找“ 重数/漏数 ”问题 二分法实现

第 2 章第 2 题找“ 重数/漏数 ”问题二分法实现