[理工] 105中央資演 一題

[ponponjerry (just do it)]

先上題目
https://i.imgur.com/LX0srqZ.jpg

爬過文看到以前對答案的結果是42，但我覺得很奇怪，因為他們的結論是用O(n+K)去算
，其中n=5，k=(51-15)+1

我的疑問&想法是：
1.因為每個數字的十位數都不一樣，所以直接取十位數當值域就好了(也就是先mod 10)
，這樣的話k=5，n=5

2.實際所需的空間應該不是用Big-O去算吧？在演算法中，需要count[1…k] , start[1
…k] 跟output[1…n] ，所以空間需求是k+k+n吧？

3.這個空間需求的單位應該要寫什麼呢？寫bytes感覺又怪怪的，還是寫units就好了

煩請各位回答，預祝各位考試順利！


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.70.183.56
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548488810.A.815.html
推 nchuAM37: 他題目規定要用counting了 為什麼可以mod 10
推 bmpss92196: 我也不懂為何不是k+k+n
推 sooge: 我也覺得空間是k+k+n 不知道能不能兩個都寫
推 y2j60537: 我記得如果COUNTING SORT是用結束位置做紀錄可以只用一
→ y2j60537: 個Count[k]和output[k]就做完排序
→ y2j60537: count[1...k]統計完之後用同個count[1...k]把他更新成
→ y2j60537: 結束位置
→ eggy1018: 這題大家會想要剪掉最小+1再跑嗎？可以少一點空間，不過
→ eggy1018: 好像沒什麼必要，不知道各位大大怎麼寫