d011: 例題 P-2-2. 離散化 – sort
Tags : Binary Search Sort map
Accepted rate : 277人/282人 ( 98% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-03-06 07:11

Content

假設有 $N$ 個整數要被讀到一個陣列中,我們想要將這些整數置換成從 0 開始依序排列的整數並且維持它們原來的大小關係,例如輸入的整數序列是 $(5, 3, 9, 3, 15, 9, 8, 9)$,這些數如從小到大排是 $(3, 3, 5, 8, 9, 9, 9, 15)$,去 除重複者後為 $(3, 5, 8, 9, 15)$,所以我們要替換的是:

3 ==> 0
5 ==> 1
8 ==> 2
9 ==> 3
15 => 4

所以原先的序列就會變成 $(1, 0, 3, 0, 4, 3, 2, 3)$。

Input

輸入兩行,第一行是正整數 $N$ 不超過 10 萬,

第二行是 $N$ 個整數,大小不超過 $10^9$,以空白間隔。

Output

輸出置換後的序列,兩數之間以一個空白間隔。

Sample Input #1
7
0 3 9 3 3 -1 0
Sample Output #1
1 2 3 2 2 0 1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
Tags:
Binary Search Sort map
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


ID User Problem Subject Hit Post Date
100
wubaie (小億)
d011
312 2021-12-06 21:56
80
spng (david)
d011
python 解題影片
410 2021-06-10 11:23