[理工] 105中央资演 一题

楼主: ponponjerry (ponpon)   2019-01-26 15:46:47
先上题目
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就好了
烦请各位回答,预祝各位考试顺利!
作者: nchuAM37 (应数37)   2019-01-26 17:09:00
他题目规定要用counting了 为什么可以mod 10
作者: bmpss92196 (bmpss92196)   2019-01-26 17:19:00
我也不懂为何不是k+k+n
作者: sooge (老衲)   2019-01-26 18:31:00
我也觉得空间是k+k+n 不知道能不能两个都写
作者: y2j60537 (skkkkuu)   2019-01-26 18:52:00
我记得如果COUNTING SORT是用结束位置做纪录可以只用一个Count[k]和output[k]就做完排序count[1...k]统计完之后用同个count[1...k]把他更新成结束位置
作者: eggy1018 (羅密歐與豬過夜)   2019-01-27 01:21:00
这题大家会想要剪掉最小+1再跑吗?可以少一点空间,不过好像没什么必要,不知道各位大大怎么写

Links booklink

Contact Us: admin [ a t ] ucptt.com