DIUs

编程之美第2.3题————寻找发帖“水王”

题目描述：

Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说，Tango有一大“水王”，他不但喜欢发贴，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？

首先，我们可以假设有这样一个数据结构来表示帖子

[cpp]
type struct post
{
char* title;
char* content;
int uid;
}post_t;
[/cpp]

题目告诉我们已知所有帖子的列表，也就是说我们知道了所有帖子的链表 post_t*　post_list，或者是所有帖子的数组post_array[num]。然后让我们找到出现次数最多的uid是多少，并且该uid一定超过了总和的一半。为了叙述方便，下面用数组举例。最容易就想到的方法，就是遍历整个数组，记录每一个uid出现的次数，然后再比较一下，求出最大的。

其实，这个问题就可以等价于：求数组中出现次数大于一半的那个数

解法一

对数组排序，然后遍历排好序的数组，统计各ID出现的次数，找到超过一半的那个即可。代码如下：

[cpp]
int Find (int* post, int len)
{
sort(post, post + len);

int num = 1;
for(int i = 0; i < len; i++)
{
if(post[i] == post[i + 1])
num++;
else
num = 1;
if(num > len / 2)
return post[i];
}
return 0;
}
[/cpp]

这里先调用了一下sort函数排序，也可以换成自己的排序函数。

因为采用了排序，复杂度有所提升，于是书中提出了第二种解法，我觉得是比较巧妙的。

解法二

由于x出现的次数大于总数的一半，所以如果每次删除两个不同的值，不管是否有x，在剩下的数中，x的次数依然会大于总数的一半。

于是，算法可以这样设计

[cpp]
int Find2 (int* post, int len)
{
int x;
int times = 0;
for(int i = 0; i < len; i++)
{
if(times == 0)
{
x = post[i];
times = 1;
}
else
{
if(x == post[i])
times++;
else
times–;
}
}
return x;
}
[/cpp]

该算法不用排序，很巧妙的通过向前移动达到了“删除”的目的，自己真的没想到：）。

越来越觉得优美的代码就是美了，简洁明了，而又功能强大。

扩展问题：

随着Tango的发展，管理员发现，“超级水王”没有了。统计结果表明，有3个发帖很多的ID，他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗？

解法x

这个思路就是一样的了，设a，b，c三人的发帖数都超过了 1/4，那么把4个不同id删除以后，并不影响剩余数组中a，b，c三人的发帖数都超过1/4这个结果。示意图如下所示。

把数组分为四个四个数字一组的来看。由于a的发帖数超过了1/4，所以，平均下来，在每一个分组里都有一个a，并且至少在某一组中有大于一个的a，假如分组1中的四个数字都不相同，我们删除分组1，如果a不在分组1里面，那么在剩余的2~n组中，a出现的次数显然会继续大于1/4；如果a在分组1里面，那么在剩余2~n组中，平均下来，a还是会至少在每一个分组出现一次。所以只要分组1中4个数字不相同（主要是保证没有两个a），那么删除分组1，并不改变a在剩余数组中出现次数依然大于1/4的事实。同理b，c。

代码如下：

[cpp]
void Findx(int* post, int len)
{
int a, b, c;
int ta = 0;
int tb = 0;
int tc = 0;

for(int i = 0; i < len; i++)
{
if(ta == 0)
{
a = post[i];
ta++;
}
else if(a == post[i])
ta++;
else if(tb == 0)
{
b = post[i];
tb++;
}
else if(b == post[i])
tb++;
else if(tc == 0)
{
c = post[i];
tc++;
}
else if(c == post[i])
tc++;
else
{
ta–;
tb–;
tc–;
}
}

cout << "a: " << a << "\t";
cout << "b: " << b << "\t";
cout << "c: " << c << "\t";
}
[/cpp]

Enjoy!

编程之美第2.1题————求二进制数中1的个数

题目描述：对于一个字节（8bit）的无符号整形变量，求其中的二进制表示中“1”的个数，要求算法的执行效率尽可能的高。

书中由浅入深地给出了几种解法。

解法一

也是最容易想到的，因为对于无符号整数，若采取对2取余操作，结果只有两种，奇数余1，偶数余0，而奇数的二进制最后一位为1，偶数的二进制最后一位为0。这样我们就可以通过奇偶判断来得到结果，以二进制数1011和1100举例：

1011 对2取余，余数为1，二进制末尾为1，即含有一个1

1100 对2取余，余数为0，二进制末尾为0，即含有一个0

不管这个二进制数的高位有多少个0或者多少个1，对2取余的操作只与最低位相关。所以，如果能够把所有的位都作为最低位，对2取余一次，然后将结果相加，即可得到该题答案。而二进制数中，右移操作，就相当于除以2，所以有了以下解法。

[c]
unsigned int Count (unsigned int x)
{
unsigned int num = 0; // the result
while(x) // end of loop when x is 0
{
if(x % 2 == 1) // to judge whether the last bit is ‘1’
{
num++;
}
x = x / 2; // same as x >> 1
}
return num;
}
[/c]

当然你要是觉得除法耗费时间，可以把x = x / 2改成 x >> 1，本质上是一样的。

解法二

既然提到了右移，就能想到，右移的时候会把最后一位移丢，那我们只要在每一次移动的时候，判断一下最后一位是否为1，然后重复该步骤直到将所有位都移除。用1011举例：
1011，最后一位是1，结果加1，右移一位，变成0101

0101，最后一位是1，结果加1，右移一位，变成0010,

0010，最后一位是0，结果不加，右移一位，变成0001，

0001，最后移位是1，结果加1，右移一位，变成0000，所有位都已移除，结束算法。

而判断最后一位是否为1，可以用&操作，x & 0x1 即可。

算法如下：

[cpp]
unsigned int Count2 (unsigned int x)
{
unsigned int num = 0; // the result
while(x) // end the loop when x is 0
{
// x & 0x01 will be 0 if the last bit is ‘0’, otherwise ‘1’
num = num + (x & 0x01);
x = x >> 1; // right shift 1 bit
}
return num;
}
[/cpp]

可以看到，上述两种解法对每一位都进行了比较运算，时间复杂度都为O(log₂^x)，出于降低时间复杂度的角度，书中又给出了第三种解法，让复杂度只与二进制数中‘1’的个数相关。

解法三

该解法确实好玩儿，让我有一种“让广大码农飞，让搞算法的死”的感觉，很巧妙。还是先举一个例子来阐述原理：对于无符号一个二进制数x，与 x – 1 采取&操作会消除x最低位的1，假设x为1010,0000：

x – 1 的二进制为 1001,1111，与x进行&以后得1000,0000，最低位的1没有了，让x = 1000,0000

x – 1 的二进制位 0111,1111，与x进行&作以后得0000,0000，最低位的1没有了，x 为0，结束算法

算法一共就执行了两次，即‘1’的个数。不管‘1’之后有多少个0，x & (x – 1) 总是会消除最低位的1，这就是该算法的巧妙之处了。代码如下。

[cpp]
unsigned int Count3 (unsigned int x)
{
unsigned int num = 0;
while(x)
{
x = x & (x – 1);
num++
}
return num;
}
[/cpp]

算法把时间复杂度降到了O(n)，n为二进制中‘1’的个数。应该算是很不错了，关键是很巧妙，灰常好玩儿有木有。

书中还给出了查表法，因为题目是八位的二进制，那么一共也才256个数，完全可以开一个256大小的数组，将结果存起来，如255的二进制为1111,1111，让result[255] = 8，同理把其他所有数的结果都存一遍，以后需要的时候直接返回result[x]就可以了。只是如果不是八位的，变成了32位，那查表这种空间换时间的方法就很不划算了。

后来查阅网上一些题解的时候，发现很多大牛对此题书中解法的提出了质疑。比如解法三，虽然理论上一次地址计算就可以解决，但实际上这里用到一个访存操作，且第一次访存的时候很有可能那个数组不在cache里，这样一个cache miss导致的后果可能就是耗去几十甚至上百个时钟周期（因为要访问内存）。而对于这种数据规模给定，而且很小的情况下，耗去几十甚至上百个时钟周期是很慢的。所以对于这种“小操作”，这个算法的性能其实是很差的。

然后我看到了另外一个巧妙的解法，有点像二分，个人灰常喜欢。

解法X

怎么说呢，先举个例子，比如整数212的二进制1101,0100，一共有4个‘1’对吧。而正好又是8位大小，有没有一种“对折对折再对折”的冲动，有木有？

于是算法可以这样描述：

先把相邻的‘1’的个数算出来，同样二进制的形势保存起来

那么现在 10,01,01,00分别代表了1101,0100中相邻两位中‘1’的个数。而且由于是计算的相邻两位，所以‘1’的个数最多为2，所以用两位足够表示。

现在的问题变成了，如何继续处理第一步得到的结果1001,0100呢，对于1001,0100，

第8位，第7位联合起来,即10，表示了原二进制数（1101,0100）中第8位与第7位所含‘1’的个数。

第6位，第5位联合起来,即01，表示了原二进制数（1101,0100）中第6位与第5位所含‘1’的个数。

第4位，第3位联合起来,即01，表示了原二进制数（1101,0100）中第4位与第3位所含‘1’的个数。

第2位，第1位联合起来,即01，表示了原二进制数（1101,0100）中第2位与第1位所含‘1’的个数。

现在我们就需要把新得到的二进制串1001,0100的

8、7联合位与6、5联合位相加，即把10和01相加，代表原第8,7,6,5位的‘1’的个数

（因为8、7联合起来才表示原第8位和原第7位一共有多少个‘1’，这里不能再次分开计算他们了，应该把他们当成一个整体。同理6、5位，也当成一个整体来看待）

4、3联合位与2、1联合位相加，即把01和01相加，代表原第4,3,2,1位的‘1’的个数

后面就类似啦，把0011与0001相加，代表原第8,7,6,5,4,3,2,1位的‘1’的个数

就得到最后的结果了，结果为4。

好了，现在剩下的问题就是怎么样让相邻的位相加，怎么样让相邻两位的相加，怎么样让相邻四位的相加。

拿相邻两位的相加举例，

(x & 0x55) + (x >> 1  & 0x55)

因为0x55展开成二进制就是0101,0101，观察1的位置，奇数位为1，偶数位为0，这样和x进行与操作的结果就是保留了x的奇数位。然后x右移一位以后，再与0x55进行与操作，对x>>1来说是保留了奇数位，但相对于原来的x则是保留了偶数位。最后将两式相加，就得到了x的二进制中，相邻两位的‘1’的个数。

同理因为0x33展开成二进制是0011,0011，所以相邻二位的相加则为

(x & 0x33) + (x >> 2 &  0x33)

因为0x0f展开成二进制是0000,1111，所以相邻四位的相加则为

(x & 0x0f) + (x >> 4 &  0x0f)

所以算法如下：

[cpp]
unsigned int CountX (unsigned int x)
{
x = (x & 0x55) + (x >> 1 & 0x55);
x = (x & 0x33) + (x >> 2 & 0x33);
x = (x & 0x0f) + (x >> 4 & 0x0f);
return x;
}
[/cpp]

优美的代码总是很简洁，这个算法估计只要十几行指令吧，速度应该是很不错了，至于网上其他更好的算法，写得让我半天看不懂哈哈~~感觉太复杂了也就失去了美。

最后，POJ的相关题目有Problem2453

原题链接：http://poj.org/problem?id=2453

解题报告：http://keping.me/poj2453/

That’s all,

Enjoy!