Knight.Liao's Tale

编程之美2.1节中的扩展题第1题：如果变量是32位的Dword，则如何统计该二进制数中1的个数。

对于该题，我原本的想法还是想采用书中解法三，也就是用统计1中个数的算法v&(v-1)，该算法时间复杂度为该32二进制数中“1”的个数。

后来，我参见了[1]中的解法，该解法甚妙，复杂度只有若干个位运算，与“1”的数目无关。由于[1]写的比较难懂，所以在这里解释一下他的解法。

解法一：

int Count(unsigned x)
{
   x = x - ((x >> 1) & 0x55555555);  // 1
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);   // 2
   x = (x + (x >> 4)) & 0x0F0F0F0F;    //3
   x = x + (x >> 8);   //4
   x = x + (x >> 16);   //5
   return x & 0x0000003F;  // 6
}

我们以0000 0000 0000 0000 0000 0000 1011 0101为例

第一行中，x>>1是右移一位，(x>>1) 为 0000 0000 0000 0000 0000 0000 0101 1010
该结果与0101 0101 0101 0101 0101 0101 0101 0101相与，等于 0000 0000 0000 0000 0000 0000 0101 0000
实际上，((x >> 1) & 0x55555555) 该步是想得到原数据x的偶数位的数据。（代码是先右移，再得奇数位，这个等价于：先得偶数位，再右移）
继续阅读

这是编程之美书第2.5节的一道题目。

各种解法：

解法一，用nlgn复杂度的排序算法对数组进行从大到小排序，取前K个。但这方法做了两件不必要做的事：它对想得到的K个数进行了排序，对不想得到的n-K个数也进行了排序。方法不可取。

解法二，用选择排序或冒泡排序，复杂度O(NK)。但这方法也做了不必要做的一件事：对想得到的K个数进行了排序。方法不可取。

解法三，用顺序统计位（类快排）算法来计算（可参考算法导论）。算法导论上说这种方法从平均性能上来讲是线性的，但编程之美上却说复杂度是O(N*lgK)。对于这点，我对编程之美持怀疑态度。我认为，对于一个无序的数组，用顺序统计位算法，可以在近似O(n)的时间复杂度内得到第K大的元素。当这个过程执行完毕时，数组中位于该元素之前的元素就是前K大的元素。

解法三，先查找出数组中的Vmax和Vmin，组成新的数组[Vmin,Vmax]，二分查找该数组，并在原数组中查找。具体请参见编程之美。复杂度为O(nlgn)，方法不可取。

解法四，维护一个K大小的数组A，遍历原数组中的每个数，与A每个元素进行比较，如果大于A数组中的最小元素，则交换，否则继续。复杂度为O(NK)，方法不可取。

解法五，维护一个最小堆，大小为K。一开始先从原数组中随便取K个元素建最小堆，复杂度为O(K)。然后遍历原数组中剩余的n-K个元素，每个元素先与堆顶比较，如果大于堆顶则交换，并维护最小堆性质。总复杂度为K+(n-K)lgK = nlgK。该方法只需要遍历一次数组，且无须在内存中存储所有数组数据，而只需维护K大小的数据。是一种适用于 大数据，小内存的好方法。如果K还是太大，则分次来求，通过先用K'（K'<K）来求……具体请参见编程之美。[1]

继续阅读

本程序实现单链表的一些稍微高级一点的操作：

• 查找单链表倒数第n个元素的值
• 查找单链表中间元素的值(中间值可能有两个)
• 一个单向的链表,知道只有一个指向某个节点的指针p，并且假设这个节点不是尾节点，试编程实现删除此节点

具体算法是：

4、在查找单链表倒数第n个元素时,有三种方法
第一种是规尺法，即利用两个步长为n的指针,同时前进直至第一个指针到达终点,那么第二个指针所指的对象就是想要得到的值,时间复杂度为O(2*N),空间复杂度为0
第二种是构造一个先进先出队列(指针队列),大小为n,遍历单链表,将遍历到的单链表结点的地址逐个存进队列中,直至单链表遍历结束.那么,这个队列的最后一个元素就是想要得到的数据,时间复杂度为O(N),空间复杂度为O(n)
第三种方法可以先逆置该链表,然后顺序取第n个元素作为结果返回,最后再次逆置链表时间复杂度为O(3*N),空间复杂度为0

5、用最快的方法求出单链表中间的元素
用二个指针,一开始同时指向链表头,然后同时往后走,第一个指针走二步,第二个指针走一步,那么,当第一个指针走到头时,第二个指针所指向的就是需要返回的值。当单链表元素个数为单数,中间元素值其实是有二个.可以通过这样来判断:当第一个指针走二步刚好是NULL,则说明单链表有偶数个元素,则应该返回二个中间值当第一个指针走一步刚才是NULL,则说明单链表有奇数个元素,则应该返回一个中间值。

继续阅读

本程序实现了一个单链表类，该类演示了单链表的以下几个操作：

• 头插法创建单链表
• 尾插法创建单链表
• 逆置单链表
• 打印、释放单链表

程序清单如下：

KnightList.h 头文件
继续阅读