在O(n)时间复杂度O(1)空间复杂度求一个数组中出现多次和未出现的数字

Question

爱奇艺笔试题：

原题是：已知一个数组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;
}

问题是：怎么想到的？什么原理

Answer 1

刚没看到已经有程序了。按题目中的程序的做法，是将数字i出现的次数加到a[i]的"高位"上去,以后查询的时候查询其"高位"即可。所谓的"高位"，可以看做时N进制数的第1位(从右向左排位，0开始)