我使用long
类型来存储数字并使用普通排序方法进行排序,但效率不够。
我认为 long(raw_input())
花费了太多时间。
有人能想出一种有效的方法来解决这个问题吗?
n = int(raw_input().strip())
unsorted = []
for i in xrange(n):
term = long(raw_input())
unsorted.append(term)
for i in sorted(unsorted):
print i
最佳答案
既然你说这是一个竞争性的编程问题,那么这个解决方案就可以工作,否则它永远不会工作,因为它需要太多的内存,并且在糟糕的情况下会崩溃。但在竞争性编程中,限制并不那么大,它应该有效。
我们只是添加比较器,即 gt 和 lt 方法来决定两个对象之间的比较。
class VeryBigNumber(object):
def __init__(self,number_string):
self.number = number_string
def __gt__(self,other):
if len(self.number)>len(other.number):
return True
elif len(self.number)<len(other.number):
return False
for i in xrange(min(len(self.number),len(other.number))):
if int(self.number[i])>int(other.number[i]):
return True
elif int(self.number[i])<int(other.number[i]):
return False
return False
def __eq__(self,other):
return self.number == other.number
def __lt__(self,other):
return not (self.__eq__(other) or self.__gt__(other))
arr = []
for i in xrange(n):
arr.append(VeryBigNumber(raw_input().strip())
arr = sorted(arr)
for a in arr:
print a.number,
大解释:
在评论中您曾说过这是为了编程比赛。这确保了内存足够小,可以在一秒钟内读入。
我们不会将这么大的字符串转换为数字,因为这是不必要的。相反,我们保持字符串原样。
那我们如何排序呢?我们创建自己的类并使用字符串比较。
这些工作原理是比较字符串之间的字符数字,因此一次只有一个字符转换为 int,这是非常高效的。
我已经测试了上面的代码,它可以正常工作
关于python - 在 Python 2 中对 10**6 位数字进行高效排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42397729/