空间换时间- - -据说著名外企试题
时间：2010-03-29 来源：liuyuanyang
问题：对于一个字节（8bit）的数据，求其中“1”的个数，要求算法的执行效率尽可能地高。
#include
#define BYTE unsigned char
/* 定义查找表 */
BYTE numTable[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,
4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,
5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3,
4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,
4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,
7, 6, 7, 7, 8
};
int main(int argc, char *argv[])
{
int i, num = 0;
BYTE a = 0;
/* 接收用户输入 */
printf("\nPlease Input a BYTE(0~255):");
scanf("%d", &a);
/* 计算1 的个数 */
/* 用BYTE 直接作为数组的下标取出1 的个数，妙哉！ */
printf("\nthe num of 1 in the BYTE is %d", checknum[a]);
return 0;
}
这是个典型的空间换时间算法，把0~255 中1 的个数直接存储在数组中，字节a 作为数组的下标，checknum[a]直接就是a 中“1”的个数！算法的复杂度如下：
时间复杂度：O(1)
空间复杂度：O(2n)
恭喜你，你已经被这家著名的外企录用！老总向你伸出手，说：“Welcome to our company”。
相关阅读 更多 +
