[HackerRank]計數排序3(Counting Sort 3)

題目描述

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

原題網址

輸入格式

第一行是陣列的大小N，範圍在100到10⁶之間(包含100和10⁶)。接下來的N行每行都是由一個整數和一個字串組成的陣列元素，整數範圍在0到100之間(包含0，但不包含100)，字串長度在1到10之間(包含1和10)。

輸出格式

分別計算並輸出整數小於或等於0到99(包含0和99)的元素數量，用空白字元分隔。

範例輸入

範例輸出

額外解釋

「0」出現了1次，所以輸出「1」。「0」和「1」共出現3次，所以輸出「3」。「0」、「1」、「2」共出現5次，所以輸出「5」。依此類推，共會輸出100個累計數量。

解題概念

與這個題目不同的是，此題需要另外在計數時將字串儲存到另一個陣列之對應位置上(之後排序時會用到)，並在輸出數量時進行累加的動作。

參考答案

import java.util.*;

public class Solution {

    public static void main(final String[] args) {
        final Scanner in = new Scanner(System.in);
        final int n = Integer.parseInt(in.nextLine());

        final int[] A = new int[n];
        final String[] S = new String[n];
        final int[] count = new int[100];
        for (int i = 0; i < n; ++i) {
            final String[] tokens = in.nextLine().split(" ");
            A[i] = Integer.parseInt(tokens[0]);
            S[i] = tokens[1];
            ++count[A[i]];
        }
        final StringBuilder sb = new StringBuilder();
        int sum = 0;
        for (int i = 0; i < 100; ++i) {
            sum += count[i];
            sb.append(sum).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}