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，
回答 2
Stack Overflow用户
回答已采纳
发布于 2020-05-11 14:58:27
这将在给定的约束下工作。假设字符串只由小写和大写字母组成。
for _ in range(int(input().strip())):
N, Q = map(int, input().strip().split())
s = input().strip()
frequencies = [0] * 26
[frequencies.__setitem__(ord(k) - 97, frequencies[ord(k) - 97] + 1) for k in list(s)]
# To get something like [4,4,1,2,0,0,0,0,0,....]
counts = list(sorted(filter(lambda x: x > 0, frequencies)))
# counts = [1,2,4,4]
for __ in range(N):
C = int(input().strip())
# Find the index of the value just greater in counts.
for i, c in enumerate(counts):
if c > C:
break
if i >= 0 and i < len(counts): # If i is within range. Print the sum from thereon.
print(max(sum(counts[i:]) - C * len(counts[i:]), 0)) # Subtract C from the individual counts
else:
print(0)并回答为什么你的代码超过了时间限制。您正在迭代整个字符串s。在查询的for循环中。
因此，如果使用len(s)=10^5和len(N)=10^5，您将进行10^10迭代。或O(n^2)
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
复制相关文章
相似问题
腾讯云开发者
