作者ponponjerry (just do it)
看板Grad-ProbAsk
标题[理工] 105中央资演 一题
时间Sat Jan 26 15:46:47 2019
先上题目
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548488810.A.815.html
1F：推 nchuAM37: 他题目规定要用counting了 为什麽可以mod 10 01/26 17:09
2F：推 bmpss92196: 我也不懂为何不是k+k+n 01/26 17:19
3F：推 sooge: 我也觉得空间是k+k+n 不知道能不能两个都写 01/26 18:31
4F：推 y2j60537: 我记得如果COUNTING SORT是用结束位置做纪录可以只用一 01/26 18:52
5F：→ y2j60537: 个Count[k]和output[k]就做完排序 01/26 18:52
6F：→ y2j60537: count[1...k]统计完之後用同个count[1...k]把他更新成 01/26 18:55
7F：→ y2j60537: 结束位置 01/26 18:55
8F：→ eggy1018: 这题大家会想要剪掉最小+1再跑吗？可以少一点空间，不过 01/27 01:21
9F：→ eggy1018: 好像没什麽必要，不知道各位大大怎麽写 01/27 01:21