題目描述
快速排序法的時間複雜度為O(nlog2n)，還有什麼演算法可以排序更快呢？一般來說，大部分的演算法都需要進行「比較」，所以在最差的案例下最快也是需要nlog2n的執行時間。然而在某種類型的輸入條件下，使用「非比較」的演算法會更有效率，只需要線性時間就可以完成計算。給定一個整數陣列，請算出各數值出現的次數。
原題網址
輸入格式
輸入有兩行，第一行是陣列的大小，範圍在100到106之間(包含100和106)。第二行是整數陣列的內容，用空白字元分開各個整數，整數範圍在0到100之間(包含0，但不包含100)。
輸出格式
個別輸出數字0到99(包含0和99)的出現次數，用空白字元分隔。
範例輸入
100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33
範例輸出
0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2
額外解釋
「0」出現了0次，「1」出現了2次，「2」出現了0次，依此類推。
解題概念
宣告並實體化出一個長度為100的整數陣列，預設元素數值均為0。緊接著從標準輸入中讀入陣列內容，並同時利用那個長度為100的整數陣列統計0到99數字出現的次數。最後再把那個長度為100的整數陣列輸出。
參考答案
import java.util.*;
public class Solution {
public static void main(final String[] args) {
final Scanner in = new Scanner(System.in);
final int n = in.nextInt();
final int[] A = new int[n];
final int[] count = new int[100];
for (int i = 0; i < n; ++i) {
A[i] = in.nextInt();
++count[A[i]];
}
final StringBuilder sb = new StringBuilder();
for (int i = 0; i < 100; ++i) {
sb.append(count[i]).append(" ");
}
System.out.println(sb.toString().trim());
}
}