一个时间复杂度和空间复杂度限定的问题

Question

待字闺中的微信公共帐号上看到的，时间复杂度O(n)、空间复杂度O(n)能想出来。O(1)的想不出来呀。
给定数组A，大小为n，数组元素为1到n的数字，不过有的数字出现了多次，有的数字没有出现。请给出算法和程序，统计哪些数字没有出现，哪些数字出现了多少次。能够在O(n)的时间复杂度，O(1)的空间复杂度要求下完成么？

Answer 1

算法代码，Python#encoding:utf-8'''Createdon2013年9月13日'''importsysdefmain():a=[1,2,3,4,4,6,7,7,9]n=len(a)fork,vinenumerate(a):a[k]=v*nprintafork,vinenumerate(a):a[(v/n-1)]+=1printafork,vinenumerate(a):a[k]=a[k]%nomitted=[]duplicated=[]fork,iinenumerate(a):ifi1:duplicated.append(k+1)printomittedprintduplicatedif__name__=='__main__':sys.exit(main())