題目描述

一個已排序的清單，用來作為排序依據的元素常常只是其他值的某個鍵值或是屬性。舉例來說，如果您正在根據檔案大小來排序檔案，檔案的大小必須跟它們所對應的檔案互相連結。您不能只單純地排序檔案大小，然後將其輸出，您會需要輸出跟這些檔案有關的必要資訊。然而，如果您真的不需要其他資訊，您可以簡單的排序那些數值就好，這也可以讓計數排序變得更加容易。如果您已經計算過清單中數值出現的次數，那麼您就不用再去存取原本的清單。給定一個整數陣列，請依照數值順序輸出這些整數。



原題網址

https://www.hackerrank.com/challenges/countingsort2

輸入格式

輸入有兩行，第一行是陣列的大小，範圍在100到106之間(包含100和106)。第二行是整數陣列的內容，用空白字元分開各個整數，整數範圍在0到100之間(包含0，但不包含100)。

輸出格式

使用計數排序，排序陣列後依序輸出陣列中的元素，用空白字元分隔。

範例輸入

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

範例輸出

1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 44 44 46 46 48 50 53 56 56 57 59 60 61 63 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 90 91 92 94 95 96 98 98 99 99

解題概念

根據這個題目所解答出來的程式，我們可以得知陣列中各個元素的出現次數，接著就可以直接利用這個次數，來將元素數值從小到大依序、依次輸出，就是陣列排序後的結果了。舉例來說，假設陣列有3個「2」，2個「1」，不管元素在原始陣列中的順序是怎樣，既然我們已經知道每個元素的出現次數，輸出時就先輸出2個「1」，再輸出3個「2」，就是陣列最終排序後的結果了。

參考答案

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) {
            final int v = count[i];
            if (v > 0) {
                for (int j = 0; j < v; ++j) {
                    sb.append(i).append(" ");
                }
            }
        }
        System.out.println(sb.toString().trim());
    }
}