哪些数字没有出现

给定数组A,大小为n,数组元素为1到n的数字,不过有的数字出现了多次,有的数字没有出现。请给出算法和程序,统计哪些数字没有出现,哪些数字出现了多少次。能够在O(n)的时间复杂度,O(1)的空间复杂度要求下完成么？

初步分析

假如没有空间复杂度的限制,很简单地,我们可以想到的开一个空数组B,遍历一遍数组B,执行B[A[i]]++操作即可知道数组A中哪些元素没有,哪些元素出现了多次。可现在空间复杂度要求为O(1),这意味着我们只能在原数组上进行数据操作。

遇到困难

既然是在原数组上进行操作,如果我们能够让数组A的第A[i]个位置的值加一,那么加一处理后的A’减去原来的A就得到结果,可这个算法需要额外的存储空间A’来存储原来的A,况且我们也不方便在遍历时对A[A[i]]进行操作,因为下标 A[i]的值在遍历过程中可能发生改变,因而变得不可预知.

解决方案1

@HanruiGao给出了如下解答.
我们对数组进行三次遍历(数组下标从1到n)

A[i] *= (n+1);
A[A[i]/(n+1)]++;
输出A[i]%(n+1)即得结果.

第一次遍历,对A[i]进行预处理,为了表述方便,我们记这个新的数组为 $ A^* $ ,即 $ A^* [i]=(n+1)A[i] $
这样在第二次遍历时,下标 $ \dfrac{A^*[i]}{n+1} $ 的值一定会是原来的A[i],因为对于任意的: $ 1\leq k_i\leq n $

我们都有

这就是第一步要乘以n+1的原因了(事实上这里的n+1取n即可,因为k_i取不到n,当然取任意大于n的整数都行).通过这种先乘后除的方法,我们就解决了刚才分析过程中下标动态变化的问题.
第二次遍历结束后,此时$A^* [i]=(n+1)A[i]+k_i$,这里的$k_i$就是i出现的次数,我们不需要额外的存储空间来得到$k_i$,而是直接对第二次遍历结束后的$A^* $求模,

就能够得到每一个元素出现的次数了.

解决方案2

刚才我们通过先乘以一个大整数再除以它的方法来维护数组的下标,现在我们介绍另一种方法。
取一个整数M(M>n),对数组进行两次遍历：

A[A[i]%M] += M;
输出A[i]/M.

第一次遍历,所有的A[i]变成了 $A[i]+k_i\times M$ ,其中A[i]<M,这里的k_i就是我们统计的频数。并且在修改A[i]的过程中,我们通过取模运算仍然保证了下标 $A[i]\%M$ 就是改变之前的$A[i]$;第二次遍历用除把它提取出来：