【编程珠玑】第二章：二分查找的巧妙应用
一，三个问题
A题：给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。
1、在文件中至少存在这样一个数？
2、如果有足够的内存，如何处理？
3、如果内存不足，仅可以用文件来进行处理，如何处理？
答案：
1、32位整数，包括-2146473648~~2146473647，约42亿个整数，而文件中只有40亿个，必然有整数少了。
2、如果采用位数思想来存放，则32位整数最多需要占用43亿个位。约512MB的内存空间 (2`32/8=512MB)
可以采用前一章的位处理方法。然后判断每个int是否等于-1。因为-1的二进制表示是全1的。如果不等于-1。那么说明某一位没有置位。需要进行处理。
3、内存不足，可以采用如下思想：
按最高位分为两段，没有出现的那个数，肯定在比较小的段里面。
如果比较少的段最高位为1，那么缺少的那个数的最高位也为1.
如果比较少的段最高位为0，那么少的那个数的最高位也是0.
依次按以上方法去处理每个位。
算法复杂度为O(n)。每次处理的部分都是上一次的一半。累加之后是O(n).
思想与找第K小数的思想是一样的。只不过在这里是有一个自动分割的过程。而找第k小数的时候，是随机找一个数。
为了验证思想这里写了段C代码。
[html]
int get_lost(int *a, int *b, int *c, int alen, int bit)
{
int re = 0, v = 0, biter = 0, *t, citer, i = 0;
if (!a || !b || alen ==(unsigned long)( (1<< bit))) return -1; //哪个数与最多可能拥有个数相等的时候，直接返回了。
while (bit--)
{
v = (1 << bit);
for (biter = citer = i = 0; i < alen; ++i)
{
if (a[i] & (1 << bit)) b[biter++] = a[i];
else c[citer++] = a[i];
}
if (biter <= citer)
{
re += v;
t = a; a = b; b = t;
alen = biter;
}
else
{
t = a; a = c; c = t;
alen = citer;
}
}
return re;
}
a, b, c,都是三个等长的数组，alen表示其长度。bit表示位数。比如32位。bit=32.
re表示最后缺少的那个数。
B题:字符串循环移位比如abcdef 左移三位,则变成defabc
_rev(0, i)
_rev(i, len)
_rev(0, len)
[html]
static void _res(char *a, int n)
{
int i = 0, j = n - 1;
char t;
while (i < j)
{
t = a[i]; a[i] = a[j]; a[j] = t;
++i; --j;
}
}
char *rever(char *a, int n, int len)
{
int i, j;
if (!a || !n) return a;
_res(a, n);
_res(a + n, len - n);
_res(a, len);
return a;
}
C 题:给定一个单词集合，找出可以相互转换的集合。比如abc bca cba都可以相互转换。(变位词)
算法如下：单词按照字母进行排序，单词间进行排序，这样相同标识的单词聚集到一起
这里用C++来写了。
[html]
void gen_label(vector<string> &dict, map<string, vector<string> >&rec)
{
for (int i = 0; i < dict.size(); ++i)
{
string line = dict[i];
sort(line.begin(), line.end());
rec[line].push_back(dict[i]);
}
for (map<string, vector<string> >::iterator iter = rec.begin();
iter != rec.end(); ++iter)
{
copy((iter->second).begin(), (iter->second).end(), ostream_iterator<string>(cout , " "));
cout << endl;
}
}
2.6习题
1 、如果没有时间进行预处理，那么可以找到这个单词的标识符，然后扫描这个字典，标识符相同的输出。
如果可以预处理，那么可以先预处理，用gen_label函数进行预处理则可。
2、[关键看清楚：顺序文件--->已经排好序的； 4300 000 000 大于2`32]
把原来的程序取较大的部分则可。实际上如果要形成严格地每次下降一半，那么需要如下处理。
如果最多有max个整数，比如对于有4个bit位的整形数。最多有16个数。
如果给了32个数，实际上只需要取前面17个数就可以了，后面的不要了。
把这17个数按首位分为两堆，按理说一边是8，一边是9。如果发现分的一边比9还要多
补充：软件开发 , 其他 ,
