计数的实现在Python中排序

我在试着这HackerRank problem。到目前为止，我已经结束了与此代码：计数的实现在Python中排序

n = int(raw_input()) 
ar = [] 

for i in xrange(n): 
    ar.append(raw_input().split()) 

output = [0] * 1000000 
count = [0] * 100 

for a in ar:  
    count[int(a[0])] += 1 

total = 0 

for a in xrange(100): 
    old = count[a] 
    count[a] = total 
    total += old 

for a in ar: 
    if ar.index(a) < n/2: 
     output[count[int(a[0])]] = '-' 
    else: 
     output[count[int(a[0])]] = a[1] 
    count[int(a[0])] += 1 

for o in output: 
    if type(o) != str: 
     break 
    else: 
     print o,

满分为5分的测试情况下，只有通过一个。 2由于运行时间过长而超时，但这不是我现在的优先事项。我的优先考虑是通过另外两个完全失败的测试用例。我无法确定我可能出错的地方。我知道我可以让我的代码更有效率，但现在，我只关注获取正确的输出。

来源

2016-05-14 Sidharth Samant

我只能运行一个测试用例而无需注册;但为了提高性能：a）在加载数据的同时，在开始时执行一次所有的int（）转换。拆分它，转换为'int（）'，然后执行'ar.append'。 b）用破折号替换前半部分时，不要使用'output [count [int（a [0]）当将前半部分加载到数组中时，知道前半部分。一半; c）不需要使'输出'那么大，使它变成'[0] * n' - 更低的内存使用。 d）也许在每个输出中跳过'type（o）'测试，然后打印o。 – TessellatingHeckler

我怀疑你的所有问题（包括时间和正确性）来自于使用ar.index(a)来检查一个值是否在输入列表的前半部分。

该行总是非常慢（搜索列表需要O（N）时间），如果有两条相同的行，一个输入的前半部分和一个输入行在下半场。相反，使用enumerate得到索引你迭代的名单：

for i, a in enumerate(ar): 
    if i < n/2: 
     output[count[int(a[0])]] = '-' 
    else: 
     output[count[int(a[0])]] = a[1] 
    count[int(a[0])] += 1

你也许可以改善其他的一些事情（像制作output长度n，或每个键转换为int只有一次），但得到摆脱电话list.index()可能是最重要的修复。

来源

2016-05-14 06:42:22 Blckknght

谢谢！ 'enumerate（）'的确有用。我也做了'输出'长度'n'。 –

计数的实现在Python中排序

回答

相关问题