学步园

给定一个长度为N的数组，其中每个元素的取值范围都是1到N。判断数组中是否有重复的数字。（原数组不必保留）

方法1.
对数组进行排序（快速，堆），然后比较相邻的元素是否相同。
时间复杂度为O(nlogn)，空间复杂度为O(1)。

方法2.
使用bitmap方法。
定义长度为N/8的char数组，每个bit表示对应数字是否出现过。遍历数组，使用 bitmap对数字是否出现进行统计。
时间复杂度为O(n)，空间复杂度为O(n)。

方法3.
遍历数组，假设第 i 个位置的数字为 j ，则通过交换将 j 换到下标为 j 的位置上。直到所有数字都出现在自己对应的下标处，或发生了冲突。
时间复杂度为O(n)，空间复杂度为O(1)。

方法3示例代码如下：

#include <cstdlib><br /> #include <iostream><br /> #include <ctime><br /> #include <algorithm><br /> using namespace std;<br /> const int MAX = 100;<br /> bool isDuplicate(int val[])<br /> {<br /> for(int i=0; i<MAX; i++)<br /> {<br /> if(val[i] != i)<br /> {<br /> if(val[i] != val[val[i]])<br /> swap(val[i], val[val[i]]);<br /> else<br /> return true;<br /> }<br /> }</p> <p> return false;<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> int val[MAX];</p> <p> srand((unsigned)time(NULL));</p> <p> cout << "init data: " << endl;<br /> for(int i=0; i<MAX; i++)<br /> {<br /> int temp = rand() % MAX;<br /> val[i] = temp;<br /> cout << temp << " ";<br /> }<br /> cout << endl;</p> <p> bool flag = isDuplicate(val);<br /> if(flag)<br /> cout << "has duplicate elem" << endl;<br /> else<br /> cout << "no duplicate elem" << endl;</p> <p> system("PAUSE");<br /> return EXIT_SUCCESS;<br /> }