題目描述
使用計數排序法依據清單上每個項目的整數數值來排序清單,並且保留整數相同之項目的原始順序。排序後依序輸出原本輸入清單之後半段項目的字串內容,前半段的項目只要輸出減號「-」即可。
原題網址
輸入格式
第一行是陣列的大小N,範圍在100到106之間(包含100和106)。接下來的N行每行都是由一個整數和一個字串組成的陣列元素,整數範圍在0到100之間(包含0,但不包含100),字串長度在1到10之間(包含1和10)。
輸出格式
將輸入的陣列排序之後,依序輸出每個元素的字串部份,使用空格字元分隔。
範例輸入
20
0 ab
6 cd
0 ef
6 gh
4 ij
0 ab
6 cd
0 ef
6 gh
0 ij
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the
0 ab
6 cd
0 ef
6 gh
4 ij
0 ab
6 cd
0 ef
6 gh
0 ij
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the
範例輸出
- - - - - to be or not to be - that is the question - - - -
額外解釋
以下是陣列排序之後的結果,可以看到整數部份為遞增狀態,且即便是擁有相同整數的元素,其字串順序也是和當初輸入的順序一樣。
0 ab(-)
0 ef(-)
0 ab(-)
0 ef(-)
0 ij(-)
0 to
1 be
1 or
2 not
2 to
3 be
4 ij(-)
4 that
4 is
4 the
5 question
6 cd(-)
6 gh(-)
6 cd(-)
6 gh(-)
0 ef(-)
0 ab(-)
0 ef(-)
0 ij(-)
0 to
1 be
1 or
2 not
2 to
3 be
4 ij(-)
4 that
4 is
4 the
5 question
6 cd(-)
6 gh(-)
6 cd(-)
6 gh(-)
原先陣列中前半段的元素,其字串部份應該要先取代成減號「-」。
解題概念
這題其實有很多不同的解法,若是參考這個題目來完成計數排序的累計計數的話,在儲存每個元素的字串部份時,需要將前半段的元素之字串改為減號「-」。有了累計計數的資訊後,再加上另一個大小為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());
}
}