確定每個元素出現在數組中的頻率？

Question

是否有一個高效的C算法計算並報告相等的元素的數目成陣列

例如，如果我們有

int Z[] = { 4, 9, 4, 10, 4, 2, 10, 1, 19, 21, 21 }; 

那麼結果應該是

elem   number 
    4   3 
    9   1 
    10   2 
    2   1 
    1   1 
    19   1 
    21   2 

Answer 1

有有很多方法可以做到這一點，每種方法都有不同的性能折衷。

首先，你可以在數組上做一個double for循環，並且對每個元素計算它出現的次數。這將花費時間O（n ），其中n是數組元素的數量。但是，它只需要空間O（1）。其次，您可以按升序對數組進行排序，這會將相同的元素分組在一起。從那裏可以很容易地看出每個元素出現的次數，因爲您可以遍歷數組一次並計算每個元素出現的連續次數。所用的運行時間和空間取決於您如何對數組進行排序。如果使用heapsort，則運行時將爲O（n log n），並且空間使用量將僅爲O（1）。如果碰巧知道數組範圍從0到U的所有元素，可以使用時間O（n + U）和空間O（U）或基數排序時間O（n log U）和空間上）。第三，你可以建立一個輔助表，存儲每個元素的頻率，並通過遍歷整個數組填充它，填寫條目。如果使用散列表，則預期運行時間將爲O（n），空間使用量也將爲O（n）。如果你知道數組元素在0到U的範圍內，你可以使用一個頻率數組，並且在時間O（n + U）和空間O（U）中解決這個問題（實質上，它將計算排序！ ）

這裏沒有明確的贏家。 Heapsort具有O（1）空間使用情況下的最佳時間複雜度。散列具有最好的整體時間複雜度，但空間使用率較低。根據數字的大小，計數或基數排序可能是最好的。

根據你的情況，看看你的實際參數是什麼，希望你可以選擇目前最適合你的解決方案。

Answer 2

這是一個有效的答案。

第一個循環將數組的數量初始化爲全零。

第二個循環掃描您的所有數字，直至數字爲零，然後掃描停止。這種方法的好處在於你可以添加一堆非零數字，以使數組變大並且程序仍然可以工作。

最後，第三個循環只是通過數字數組的計數並以很好的排序方式打印結果。

在預定義數字的數組中，不要刪除零並重新運行該程序，否則會得到意外的結果，其中可能包含分段錯誤。

#include <stdlib.h> 
    #include <stdio.h> 
    int main(){ 
     int Z[] = { 4, 9, 4, 10, 4, 2, 10, 1, 19, 21, 21, 0}; 
     int n; 
     int lowest=1; 
     int highest=100; 
     int counts[highest+1]; 
     for (n=0;n<=highest;n++){ 
     counts[n]=0; 
     } 
     int *num=Z; 
     while((int)*num != 0){ 
     counts[*num]++; 
     num++; 
     } 

     for (n=lowest;n<=highest;n++){ 
     if (counts[n] > 0){ 
      printf("%d = %d\n",n,counts[n]); 
     } 
     } 
     return 0; 
    }