YSMull
<-- Algorithm

哪些数字没有出现

给定数组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]进行预处理,为了表述方便,我们记这个新的数组为AA^*,即A[i]=(n+1)A[i]A^*[i]=(n+1)A[i]
这样在第二次遍历时,下标 A[i]n+1\dfrac{A^*[i]}{n+1}的值一定会是原来的A[i],因为对于任意的
1kin1\leq k_i\leq n
我们都有
A[i]=A[i]+kin+1 A[i]=\Big\lfloor\frac{A^*[i]+k_i}{n+1}\Big\rfloor

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

A[i]=(n+1)A[i]+ki=kimod(n+1) \begin{aligned} A^*[i] &= (n+1)A[i]+k_i \\ &= k_i \mod (n+1) \end{aligned}

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

解决方案2

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

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

第一次遍历,所有的A[i]变成了 A[i]+ki×MA[i]+k_i\times M ,其中A[i]<M,这里的k_i就是我们统计的频数。并且在修改A[i]的过程中,我们通过取模运算仍然保证了下标 A[i]%MA[i]\%M 就是改变之前的A[i]A[i];第二次遍历用除把它提取出来:
A[i]=A[i]+kiMM=kiA'[i]=\Big\lfloor\frac{A[i]+k_iM}{M}\Big\rfloor=k_i