爱奇艺笔试题：
原题是：已知一个数组A[]，大小为N，其中每个数都为1～N，请求出该数组中未出现的数字和出现多次的数字。
要求是时间复杂度为O(N)，空间复杂度为O(1)
这道题的关键点就在于空间复杂度为O(1)，本来想到的2-bitmap因为这点也不能实现了。
提示是：要善于利用%操作符
void appears(int r[], int n) {
int i;
for (i = 0; i < n; ++i)
r[(r[i] - 1) % n] += n;
cout << "未出现的数字为： ";
for (i = 0; i < n; ++i)
if ((r[i] - 1) / n == 0)
cout << i + 1 << " ";
cout << endl;
cout << "出现多次数字为： ";
for (i = 0; i < n; ++i)
if ((r[i] - 1) / n > 1)
cout << i + 1 << " ";
cout << endl;
}
问题是：怎么想到的？什么原理
刚没看到已经有程序了。按题目中的程序的做法，是将数字i出现的次数加到a[i]的"高位"上去,以后查询的时候查询其"高位"即可。所谓的"高位"，可以看做时N进制数的第1位(从右向左排位，0开始)
假设幽静存在一个数组，A[i]=i，a是1....N之间的数。现在有一个数不满足a[i]=i（实际上是a[i]=j），那么i即为不存在的数，j即为多次出现的数。
程序需要在一边构造这个数组的同时，一边输出结果。