Python:给定一个字符串s和一个整数C，我必须找到每个字母表的数字和C的差值的总和
Python:给定一个字符串s和一个整数C，我必须找到每个字母表的数字和C的差值的总和
提问于 2020-05-11 14:16:56
如果出现次数小于C，则应忽略它，即最大出现次数之和(出现次数- C,0)。例如，如果字符串是aabbaacdddd，C是2，那么输出应该是4。有4个a，4个d，2个b，因此(4-2，4-2，2-2)的和=4。有1c，但由于c>1，所以差值被认为是零。
下面是我的代码。
T = int(input())
for _ in range(0,T):
N,Q = map(int,input().split())
s = input()
#print(ord("a"))
#print(ord("z"))
for q in range(0,Q):
C = int(input())
m = [0] * 26
for i in s:
m[ord(i)-97] = m[ord(i)-97] + 1
#print(m)
ans = []
m.sort(reverse=True)
for i in m:
if i < C:
break
ans.append(i-C)
#print(ans)
print(sum(ans))在这个过程中，我得到了一个时间限制。有什么更快的方法可以做到这一点？
我更喜欢不使用内置或字典的解决方案
约束是-s中的所有字符都是小写字母，T，N，Q< 10^5，C <= 10^9，
Stack Overflow用户
发布于 2020-05-11 15:16:23
好的。首先，排序是一个禁忌，因为它会把你的复杂度推到O(n log(n))。
制作一个数组，用于计算26个字母表的数量。
然后，使用单循环计算字符串中的字母表，即O(n)。
遍历您的count数组，并应用上面所述的公式。
总体复杂度将是O(n)，我认为这是他们所需要的。
如果您想利用Python的所有功能，那么，
from collections import Counter
a = Counter(T) # it will return a dict with counts of all unique characters遍历返回的字典，您将得到您的答案。
但是，我建议您使用上面的O(n)方法。然后你的代码就会通过。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61723397
复制相关文章
相似问题
腾讯云开发者
