面试题之数组统计

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

解法一：

直接用两层遍历，O(n^2)的时间复杂度，O(1)的空间复杂度

#include <stdio.h>  
#include <stdlib.h>  
  
int main()  
{  
    int n, i, j, count = 0;     //n is The length of the Array  
    while (scanf("%d", &n) != EOF)  
    {     
        int *a = malloc(sizeof(int) * n);   
        for (i = 0; i < n; i++)  
            scanf("%d", &a[i]);  
  
        for (i = 0; i < n; i++)  
        {     
            count = 0;  
            for (j = 0; j < n; j++)  
            {     
                if (i == a[j])  
                {     
                    count++;  
                }     
            }     
            if (count == 0)  
                printf("%d does not appear in the array!\n", i);   
            else  
                printf("%d appear in the array for %d times\n", i, count);  
        }     
    }     
}

解法二：

以空间换时间的办法，用一个map数组来存放元素的计数。时间复杂度为O(n),空间复杂度为O(n)

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
  
int main()  
{  
    int n, i, j, count = 0;     //n is The length of the Array  
    while (scanf("%d", &n) != EOF)  
    {     
        int *a = malloc(sizeof(int) * n);   
        int *map = malloc(sizeof(int) *n);  
        memset(map, 0, sizeof(map));  
  
        for (i = 0; i < n; i++)  
            scanf("%d", &a[i]);  
  
        for (i = 0; i < n; i++)  
        {     
            map[a[i]]++;  
        }     
  
        for (i = 0; i < n; i++)  
        {     
            if (map[i] == 0)  
                printf("%d does not appear in the array!\n", i);   
            else  
                printf("%d appear in the array for %d times\n", i, map[i]);  
        }     
    }     
}

但上述解法都不满足题目对时间复杂度和空间复杂度的要求，因此我们想到重复利用数组A。

解法三：

三次遍历数组的方法：

第一次遍历：对于每一个A[i] = A[i] * n

第二次遍历：对于每一个i, A[A[i]/n]++

第三次遍历：对于每一个i,A[i]%n就是i出现的次数

解释：A[i]应该出现在A中的A[i]位置，乘以n、再除以n,很容易来回变换；第二次遍历，对于A[i]本来所在的位置不断增1，但绝不超出n，那么每一个i出现的次数，就是A[I]对n取余。

#include <stdio.h>  
#include <stdlib.h>  
  
int main()  
{  
    int n, i;       //n is The length of the Array  
    while (scanf("%d", &n) != EOF)  
    {     
        int *a = malloc(sizeof(int) * n);   
        for (i = 0; i < n; i++)  
            scanf("%d", &a[i]);  
  
        for (i = 0; i < n; i++)  
            a[i] = a[i] * n;  
  
        for (i = 0; i < n; i++)  
            a[a[i]/n]++;  
  
        for (i = 0; i < n; i++)  
        {     
            if (a[i] % n == 0)  
                printf("%d does not appear in the array!\n", i);   
            else  
                printf("%d appear in the array for %d times\n", i, a[i]%n);  
        }     
    }     
}

解法四：

两次遍历数组的方法：考虑A[i]，现在的位置为i,如果采用A来计数，它的位置应该是A[i]%n,找到计数位置，处理这个计数位置的办法就是加n.

第一次遍历：对A[i]的计算位置加n,加n可以保证A[i]%n的是不变的

第二次遍历：A数组，最后每一个元素表示为A[i] = x + k * n; 其中x<n,并且k就是我们要统计的频率

#include <stdio.h>  
#include <stdlib.h>  
  
int main()  
{  
    int n, i;       //n is The length of the Array  
    while (scanf("%d", &n) != EOF)  
    {     
        int *a = malloc(sizeof(int) * n);   
        for (i = 0; i < n; i++)  
            scanf("%d", &a[i]);  
  
        for (i = 0; i < n; i++)  
            a[a[i] % n] += n;  
  
        for (i = 0; i < n; i++)  
        {     
            if (a[i] / n == 0)  
                printf("%d does not appear in the array!\n", i);   
            else  
                printf("%d appear in the array for %d times\n", i, a[i]/n);  
        }     
    }     
}

补充：软件开发 , C++ ,