先来看看这个题目：数组test[X]的值所有在区间[1, 8000]中。 现要输出test中反复的数。要求:1. 不能改变原数组; 2.时间复杂度为O(X);3.除test外空间不超过1KB.
好， 我们先给出一个不限空间的解法（为了程序方便， 如果X为10, 实际上可能非常大）：
#include <iostream>
using namespace std; #define X 10
#define N 8000 // 输出反复的数字
void printDup(const int test[], int n)
{
int a[N] = {0};
int i = 0;
for(i = 0; i < n; i++)
{
a[test[i] - 1]++;
} for(i = 0; i < N; i++) // 注意， 此处是N而不是n
{
if(a[i] > 1)
{
cout << i + 1 << endl;
}
}
} int main(void)
{
int test[X] = {1, 2, 3, 4, 2, 5, 6, 7, 5, N};
printDup(test, X); return 0;
}
结果为：
2
5
显然， 上述程序在空间上超标（且当X<N=8000时。 时间超标）， 究其原因是： 让一个int去存一个二值状态， 太浪费空间了。 和不用一个bit来存呢？ 所以， 我们自然想到了用bit-map来操作。 例如以下：
#include <iostream>
using namespace std; #define X 10 #define BIT_INT 32 // 1个int能够标志32个坑
#define SHIFT 5
#define MASK 0x1f
#define N 8000
int a[1 + N / BIT_INT]; // 须要1 + N / BIT_INT 个整数来标志N个事物 // 将全部位都初始化为0状态
void setAllZero()
{
memset(a, 0, (1 + N / BIT_INT) * sizeof(int));
} // 设置第i位为1
void setOne(int i)
{
a[i >> SHIFT] |= (1 << (i & MASK));
} // 设置第i位为1
void setZero(int i)
{
a[i >> SHIFT] &= ~(1 << (i & MASK));
} // 检查第i位的值
int getState(int i)
{
return (a[i >> SHIFT] & (1 << (i & MASK))) && 1;
} // 输出反复的数字
void printDup(const int test[], int n)
{
int i = 0;
for(i = 0; i < n; i++)
{
int state = getState(test[i] - 1);
if(0 == state)
{
setOne(test[i] - 1);
}
else
{
cout << test[i] << endl;
} }
} int main(void)
{
setAllZero();
int test[X] = {1, 2, 3, 4, 2, 5, 6, 7, 5, N};
printDup(test, X); return 0;
}
结果为：
2
5
且满足题目要求。 可是。 我随后发现这个程序还有个问题: 当test数组中某元素出现次数大于2时， 会反复输出。 比方：
#include <iostream>
using namespace std; #define X 10 #define BIT_INT 32 // 1个int能够标志32个坑
#define SHIFT 5
#define MASK 0x1f
#define N 8000
int a[1 + N / BIT_INT]; // 须要1 + N / BIT_INT 个整数来标志N个事物 // 将全部位都初始化为0状态
void setAllZero()
{
memset(a, 0, (1 + N / BIT_INT) * sizeof(int));
} // 设置第i位为1
void setOne(int i)
{
a[i >> SHIFT] |= (1 << (i & MASK));
} // 设置第i位为1
void setZero(int i)
{
a[i >> SHIFT] &= ~(1 << (i & MASK));
} // 检查第i位的值
int getState(int i)
{
return (a[i >> SHIFT] & (1 << (i & MASK))) && 1;
} // 输出反复的数字
void printDup(const int test[], int n)
{
int i = 0;
for(i = 0; i < n; i++)
{
int state = getState(test[i] - 1);
if(0 == state)
{
setOne(test[i] - 1);
}
else
{
cout << test[i] << endl;
} }
} int main(void)
{
setAllZero();
int test[X] = {1, 2, 3, 4, 2, 5, 6, 2, 5, N}; // 2出现3次
printDup(test, X); return 0;
}
结果为：
2
2
5
我想了一下， 临时没有想到仅仅打印2, 5且符合题意的方法。 假设大家有好的思路， 欢迎赐教