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

Question

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

Answer 1

算法代码，Python
#encoding:utf-8
'''
Createdon2013年9月13日
'''
importsys
defmain():
a=[1,2,3,4,4,6,7,7,9]
n=len(a)
fork,vinenumerate(a):
a[k]=v*n
printa
fork,vinenumerate(a):
a[(v/n-1)]+=1
printa
fork,vinenumerate(a):
a[k]=a[k]%n
omitted=[]
duplicated=[]
fork,iinenumerate(a):
ifi<1:
omitted.append(k+1)
elifi>1:
duplicated.append(k+1)
printomitted
printduplicated
if__name__=='__main__':
sys.exit(main())