快速查找數組中元素的數量

Question

我有一個數組，大小可以達到10000.它只包含1/2/3/4。我需要找出陣列中有多少個1s，2s，3s和4s。最快的做法是什麼？我的使用語言是Java。我的一段代碼 -

for(int i=0; i<myArray.length;i++){ 
      int element = myArray[i]; 
      if(element == 1){ 
       onesCount++; 
      } 
      else if(element == 2){ 
       twosCount++; 
      } 
      else if(element == 3){ 
       threesCount++; 
      } 
      else 
       foursCount++; 
} 

我希望有一個很好的解決方案。

Answer 1

int count[5]; //initialize this to 0 
for(int i = 0; i<n; i++) 
{ 
count[array[i]]+=1; 
} 

Answer 2

您可以在數組中使用一次。

只要有自己的四個要素，分別代表你的價值觀之一（1/2/3/4）的數組和原始數組中的每個元素，你的「伯爵」陣列中增加了計數，在相應的地方。 這將使它O（n）。

Answer 3

如果您可以改爲使用地圖或自定義類。如果你不能遍歷整個數組。如果你現在不用擔心性能問題，那麼我只需要進行迭代。

Answer 4

您將擁有用於數組條目的單獨計數器。每個將在一個新的匹配數量遞增被發現，所以你必須訪問每一個指數至少一次，也就是說，你將有一個算法O（n）的時間工作。開關語句可能是首選，而不是多個if-else語句：

int[] array = new int[10000]; 
// ... populate array 
int[] counters = new int[4]; 

for (int i = 0; i < array.length; i++) 
{ 
    int temp = array[i]; 
    switch (temp) { 
    case 1: 
     counters[0]++; 
     break; 
    case 2: 
     counters[1]++; 
     break; 
    case 3: 
     counters[2]++; 
     break; 
    case 4: 
     counters[3]++; 
     break; 
    default: 
     // to do. 
    } 
} 

Answer 5

沒有解決方案比您的解決方案更好。可以更靈活，但不會更快。一切都必須至少通過整個陣列。

的性能優化的唯一區域是通過跟蹤計數器作爲陣列被更新，以避免在執行此操作，例如。如果這是值得的麻煩（可能不是）取決於你需要多久做一次這樣的事情，這個數組有多大，以及你需要做什麼。

Answer 6

如果您使用的是Java 7，則可以使用Fork/Join Framework。 的複雜性仍然是O（N）...但它可能更快的大陣

Answer 7

如果開關的版本（deporter）或遊牧的版本不是最好的，試試這個：

for (int i = 0; i < myArray.length; i++) { 
    int element = myArray[i]; 
    if (element > 2) { 
     if (element == 4) { 
      foursCount++; 
     } else 
      threesCount++; 
    } else { 
     if (element == 2) 
      twosCount++; 
     else 
      onesCount++; 
    } 
} 

它可以節省少量的比較。但這取決於真實的數據。如果你對數據感到幸運，那麼簡單的版本可能會做得更好。

除此之外，採用並行始終是值得大數據一試。

Answer 8

我不認爲你會得到比這更快：

final int[] counts = new int[5]; 
final int length = array.length - 1; 
for (int i = 0; i < length; i++) { 
    counts[array[i]]++; 
} 

注意的是，在爲循環，array.length未被引用。它被放到一個本地final int中，這樣可以避免在每次迭代中對array.length進行解引用。

我爲基準此與使用一個開關此方法..case語句，只有局部堆棧變量：

int count1 = 0; 
    int count2 = 0; 
    int count3 = 0; 
    int count4 = 0; 

    for (int i = array.length - 1; i >= 0; i--) { 
     switch (array[i]) { 
     case 1: 
      count1++; 
      break; 
     case 2: 
      count2++; 
      break; 
     case 3: 
      count3++; 
      break; 
     case 4: 
      count4++; 
      break; 
     } 
    } 

結果是第一種方法花了17300納秒，而switch..case方法了79800個納秒。 [更新：忘了劃分納秒十。我運行每種方法10次。]

注意：我做基準測試之前先提醒虛擬機。