在宿舍呆着无聊接着在hackerrank上刷水题。这道题由于排序的依据是一定范围内的整数,所以用计数排序效率应当不错。
说到计数排序,实际上思路也很常见。最常见的一个例子就是比赛或者是考试的时候要进行排名。
比如某班有3名同学考了100分,2名同学考了99分,5名同学考了98分。那么很明显,比99分高的同学一共有3名,所以考99分的同学只能是第4名了。
计数排序大概就是做了个数数每个元素前面有多少元素这个事情。先统计最高分多少分,然后依次统计各个分数的学生个数,然后以此叠加就可以统计出前面有多少个学生了。
而且由于不同分数段的学生是按照原顺序放置到新数组中的,所以在原数组中的顺序并不会被打乱,即这个算法是稳定的。这也是为什么这道题可以用计数排序解,因为并不会打乱文本的顺序。
顺便一提,这道题中的最大值max()的复杂度应该是,所以总运行时间应该是
。因为计数排序并不涉及到不同元素之间的比较,即不是比较排序,所以
的下界并不适用于计数排序。
最后附上这道题的一个无脑解。
# Enter your code here. Read input from STDIN. Print output to STDOUT n = int(raw_input()) ar = [] idx = [] out = [None]*n for _ in range(n): ar.append(raw_input().split()) ar[-1][0] = int(ar[-1][0]) idx.append(ar[-1][0]) if _<n/2: ar[-1][1] = "-" countlist = [0]*(max(idx)+1) for item in ar: countlist[item[0]]+=1 for i in range(len(countlist)-1): countlist[i+1]+=countlist[i] for item in reversed(ar): out[countlist[item[0]]-1]=item countlist[item[0]]-=1 for item in out: print item[1],