[HackerRank]完整的計數排序(The Full Counting Sort)

題目描述

使用計數排序法依據清單上每個項目的整數數值來排序清單，並且保留整數相同之項目的原始順序。排序後依序輸出原本輸入清單之後半段項目的字串內容，前半段的項目只要輸出減號「-」即可。

原題網址

輸入格式

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

輸出格式

將輸入的陣列排序之後，依序輸出每個元素的字串部份，使用空格字元分隔。

範例輸入

範例輸出

額外解釋

以下是陣列排序之後的結果，可以看到整數部份為遞增狀態，且即便是擁有相同整數的元素，其字串順序也是和當初輸入的順序一樣。

原先陣列中前半段的元素，其字串部份應該要先取代成減號「-」。

解題概念

這題其實有很多不同的解法，若是參考這個題目來完成計數排序的累計計數的話，在儲存每個元素的字串部份時，需要將前半段的元素之字串改為減號「-」。有了累計計數的資訊後，再加上另一個大小為N的字串陣列來儲存最後要輸出的結果，最後使用StringBuilder將排序後的結果輸出。

參考答案

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];
        final int n_half = n / 2;
        for (int i = 0; i < n; ++i) {
            final String[] tokens = in.nextLine().split(" ");
            A[i] = Integer.parseInt(tokens[0]);
            if (i < n_half) {
                S[i] = "-";
            } else {
                S[i] = tokens[1];
            }
            ++count[A[i]];
        }
        for (int i = 1; i < 100; ++i) {
            count[i] = count[i] + count[i - 1];
        }
        final String[] S2 = new String[n];
        for (int i = n - 1; i >= 0; --i) {
            final int a = A[i];
            S2[--count[a]] = S[i];
        }
        final StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            sb.append(S2[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}