我正在解决来自hackerrank的bigSorting()问题:
考虑一个数字字符串数组，其中每个字符串都是正数，其数字从
1到10^6不等。对数组中的元素按整数值的非降序或升序排序，并返回排序后的数组。
我知道它是这样工作的:
def bigSorting(unsorted):
return sorted(unsorted, key=int)
但是我之前没有猜到这个方法。最初我尝试如下:
def bigSorting(unsorted):
int_unsorted = [int(i) for i in unsorted]
int_sorted = sorted(int_unsorted)
return [str(i) for i in int_sorted]
然而，对于一些测试用例，它显示超出了时间限制。为什么会这样呢?
PS:我不知道确切的测试用例是什么，因为黑客等级并没有显示所有的测试用例。
我的代码如下三个步骤:
str到int的转化- 排序
int到str的转换为什么我觉得我的代码在OP也应该运行是它也是O(n log n)，但似乎仅仅是相同的时间复杂度是不够的?但是我想知道sorted(unsorted, key=int)避免了哪些转换?
Q1。第三个，int到str的转换?
Q2。如果是第1题的答案，那么它是我的代码不工作和在线sorted解决方案工作的唯一原因吗?也就是说，还有什么，我的代码是做额外的在线-sorted-解决方案?
Q3。也不会在线-sorted-解决方案做str到int转换多次在排序期间相同的数字?也就是说，每次它必须比较一个特定的数字时，它是否必须将其从str转换为int?或者sorted以这样一种方式实现，它必须将每个元素从str转换为int仅一次?
在你的代码中:
- 用
ints转换str -> int生成一个新的list。 - 将
ints重新排序为list。 - 使另一个新的
list的str，转换int --> str。
这是三个全新的(可能是大量的)具有多个转换的列表。
使用key=int排序参数在排序过程本身内部执行必要的转换，这意味着永远不会从int -> str进行昂贵的转换。
我们可以给Hacker Rank提供这样的代码，并且它通过了所有的测试:
import os
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
result = sorted((input() for _ in range(n)), key=int)
fptr.write('n'.join(result))
fptr.write('n')
fptr.close()
也许仍然不是"最佳"，但从阅读评论来看，这似乎是一个预期的选择。那些执行桶/合并排序的人没有看到太多的性能提升。
这里您正在将数字字符串列表转换为整数列表，反之亦然。
对于字符串到整数的每次转换(如'123456'到123456)都要消耗时间，并且对于字符串大小的每10倍转换将增加100倍的时间。@kellybundy在他的帖子中证明
如果in case link消失，添加代码和运行时间
from timeit import timeit
print(timeit('int("9"*10**5)', number=1))
print(timeit('int("9"*10**6)', number=1))
有运行时间
0.0568113109911792
5.422084125995752
所以我们可以说你的转换(字符串到整数)的时间复杂度是O(nnm)其中n是字符串的大小，m是列表的大小
这是你的代码花费时间的地方(转换时间和排序时间除外)。
除了原始解决方案(sorted(unsorted, key = int)使用python对字符串数值排序，它按词法顺序对它们排序，即0,1,2,3,4
def bigSorting(unsorted):
return sorted(unsorted, key= lambda x:(len(x), x))
这里的代码不需要转换元素然后排序，只需要排序。所以它需要NlogN的时间
现在是@kellybundy的一个更快的解决方案(他应该把这个作为他自己的解决方案)
def bigSorting(unsorted):
return sorted(unsorted, key= lambda x:int(x, 16))