给定一个长数值字符串数组，按升序排列

Question

我正试图解决黑客银行的问题Big Sorting：

问题陈述：

Consider an array of numeric strings where each string is a positive number with anywhere from 1 to 1000000 digits. Sort the array's elements in non-decreasing, or ascending order of their integer values and print each element of the sorted array on a new line.

Function Description

Complete the bigSorting function in the editor below. It should return the sorted string array.

bigSorting has the following parameter(s):

• unsorted: an unsorted array of integers as strings

Input Format

The first line contains an integer N, denoting the number of strings in unsorted.

Each of the N subsequent lines contains an integer string unsorted[i].

Constraints

• 1 <= N <= 200000
• Each string is guaranteed to represent a positive integer without leading zeros.
• The total number of digits across all strings in unsorted is between 1 and 1000000 (inclusive).

Output Format

Print each element of the sorted array on a new line.

我的代码：

n = int(raw_input())

unsorted = []

for _ in xrange(n):
    unsorted_item = raw_input()
    unsorted.append(unsorted_item)

result = sorted(unsorted)
print (result)

但结果却完全不同：

输入

^{pr2}$

预期输出

1
3
3
5
10
31415926535897932384626433832795

实际输出

1
10
3
3
31415926535897932384626433832795
5

Answer 1

你所做的还不够，因为你需要按文本长度排序- 首先是较短的字符串-并且按照字典顺序 弦的长度相同。因此，一个简单的解决方案是：

n = int(input())
unsorted = []
for _ in range(n):
    unsorted_item = input()
    unsorted.append(unsorted_item)

for element in sorted(unsorted, key=int):
    print(element)

Answer 2

Anatolii的解决方案无疑是最简单的一个，因为这些字符串都表示数字，它们应该按数字顺序排序。在

这里有一个替代的解决方案，它不需要将字符串解析为int：因为它们都是正的，那么具有更多位数的数字总是更大，具有相同位数的数字可以作为字符串进行比较。所以，首先我们用字符串长度进行比较，然后用通常比较字符串的方式比较长度相等的字符串。在

我们可以使用元组(len(s), s)作为比较键；它们通过第一个组件（字符串长度）进行比较，然后通过第二个组件（字符串本身）进行比较。在

result = sorted(unsorted, key=lambda s: (len(s), s))

平均来说，这是一个更有效的解决方案，因为解析int的速度很慢，但是比较字符串通常很快，因为它们通常在前几个数字内不同。在最坏的情况下，您必须比较每个数字，但是作为int总是进行解析需要查看每个数字。在

我尝试了1000个字符串的列表，这些字符串表示0到10^（10^4）范围内的数字，即长度不超过10^4位的数字；不使用int的解决方案要快上百倍：

^{pr2}$