Python按字符串排序字典可能不稳定？(在Hackerrank)

Question

我正在使用Hackerrank进行Python 3学习.

在最常见的任务中,您将获得一个仅包含小写英文字符的字符串,您需要在该字符串中找到前三个最常见的字符.

我遇到了一些问题.

我对此问题的解决方案如下:

#!/bin/python3
import sys

if __name__ == "__main__":
  s = input().strip()
  ch_dict = {}
  for ch in s:
      if ch in ch_dict : ch_dict[ch] +=1
      else: ch_dict[ch] = 1

  result = sorted(ch_dict.items(),key=lambda d:d[1],reverse=True)
  for i in result:
      if i[1] != 1:
          print(" ".join(map(str,i)))

当我在本地环境中测试此代码时,它可以工作!

但在线测试中,它可能会失败!

对于此输入:

aabbbccde

我提交了很多次,有时得到这样的正确答案:

b 3
a 2
c 2

并且还可以得到这个:

b 3
c 2
a 2

看起来好像不稳定？或者我的代码有什么关系？或者在Hackerrank环境中出了什么问题？

我怎样才能保证输出？

Answer 1

Python词典是无序的.当你迭代它们的内容时,顺序是依赖于实现的,请参阅为什么字典中的顺序和设置是任意的？

您只按值对项目进行排序,因此,如果您按任意顺序列出项目,有时候该项目('a', 2)将首先出现,有时候该('c', 2)对项目是.

如果要稳定订单,也可以通过对键进行排序来打破值之间的联系.

你的挑战说明:

按出现次数的降序对输出进行排序.
如果出现次数相同,则按升序对字符进行排序.

所以你需要先按值排序,然后按键排序,这两者之间的方向不同.

您可以通过两次排序或通过对反向分数进行排序来实现此目的:

# Sort forward by key, to produce a stable order between keys
by_key = sorted(ch_dict.items(), key=lambda d: d[0])
# Sort backward by value, ties are left in the original order, so by key
result = sorted(by_key, key=lambda d: d[1], reverse=True)

或者一步到位:

sorted(ch_dict.items(), key=lambda d: (-d[1], d[0]))

所以按负计数排序,然后按键排序,不要反转.

请注意,挑战实际上仅询问前三个字符.挑战不使用大量输入,但如果有,那么使用排序实际上是低效的.您不需要对所有键值对进行排序,只需排在前3位.您如何才能获得前三名？您可以使用堆队列,它可以有效地为您提供任何序列的前N:

import heapq

result = heapq.nsmallest(3, ch_dict.items(), key=lambda d: (-d[1], d[0]))

排序需要O(NlogN)时间(N是字典的大小),heapq需要O(NlogK)时间,N是相同的值,但K是最高项的计数; 这里是3.对于包含10,000个项目的字典,排序需要大约133k步才能完成,但堆队列只需要16k步.那将快10倍!