HackerRank中bigSorting代码超时问题求解

问题根源 #

你当前的代码把每个数值字符串转换成整数再排序，但题目允许字符串长度达到10^6位——Python虽然支持超大整数，但这种转换和后续的整数排序会产生极大的时间开销，尤其是数据量较大时，必然触发超时。

优化思路 #

正整数的大小比较可以直接通过字符串的两个规则实现，完全不需要转换为整数：

• 位数更少的字符串，对应的数值一定更小（比如"999" < "1000"）
• 位数相同时，字符串的字典序和整数的大小顺序完全一致（比如"150" < "200"，字符串直接比较结果也符合）

基于这个逻辑，我们可以直接对字符串数组排序，用长度+字符串本身作为排序的key，避免任何类型转换。

修正后的代码 #

#!/bin/python3

import sys

def bigSorting(unsorted):
    # 先按字符串长度排序，长度相同则按字符串本身排序
    return sorted(unsorted, key=lambda x: (len(x), x))

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    # 批量读取输入，比循环input()效率高得多
    data = sys.stdin.read().split()
    n = int(data[0])
    unsorted = data[1:n+1]
    
    result = bigSorting(unsorted)
    
    fptr.write('\n'.join(result))
    fptr.write('\n')
    fptr.close()

额外优化点 #

• 输入读取改用sys.stdin.read()批量读取：当输入数据量很大时，循环调用input()会产生大量IO开销，批量读取能显著提升速度
• 移除了不必要的模块导入（原代码里的math、random、re都没用到，直接删掉减少加载开销）

内容的提问来源于stack exchange，提问作者Epsilon