面試題之數組統計

題目：給定數組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);  
        }     
    }     
}