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

Question

待字闺中的微信公共帐号上看到的，时间复杂度O(n)、空间复杂度O(n)能想出来。O(1)的想不出来呀。

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

Answer 1

算法代码，Python

# encoding: utf-8
'''
Created on 2013年9月13日
'''
import sys

def main():
    a = [1, 2, 3, 4, 4, 6, 7, 7, 9]

    n = len(a)
    for k, v in enumerate(a):
        a[k] = v * n
    print a

    for k, v in enumerate(a):
        a[(v / n - 1)] += 1

    print a

    for k,v in enumerate(a):
        a[k] = a[k]%n

    omitted = []
    duplicated = []
    for k,i in enumerate(a):
        if i < 1:
            omitted.append(k+1)
        elif i > 1:
            duplicated.append(k+1)

    print omitted
    print duplicated


if __name__ == '__main__':
    sys.exit(main())

Answer 2

时间复杂度为o(n),空间复杂度为o（n）是利用hash思想，这里既然要求空间复杂度为o(1)，那就可以从数组A本身做文章，原文链接：http://www.ituring.com.cn/article/55331,简单来说，让数组A的每个数表示为A[i]=n*org + num的形式
写一个c实现的代码：

/**
 * 给定数组A，大小为n，数组元素为1到n的数字，不过有的数字出现了多次，有的数字没有出现。请给出算法和程序，统计哪些数字没有出现，哪些数字出现了多少次
 * 时间复杂度为O(N),空间复杂度为O(1)
 */

#include <stdio.h>
#include <stdlib.h>

void calCount(int *arr, int n)
{
    int i;

    for (i = 1; i <= n; i ++)
        arr[i] *= n;

    for (i = 1; i <= n; i ++)
        arr[arr[i] / n] += 1;

    // 打印出现次数
    for (i = 1; i <= n; i ++) {
        printf("%d出现次数为%d\n", i, arr[i] % n);
    }
}


int main(void)
{
    int i, n, *arr;

    while (scanf("%d", &n) != EOF) {
        arr = (int *)malloc(sizeof(int) * (n + 1));

        for (i = 1; i <= n; i ++)
            scanf("%d", arr + i);

        calCount(arr, n);

        free(arr);
    }

    return 0;
}