标签:
难度: Easy
运行时间: 48 ms
内存: 16.8 MB
class Solution:
def runeReserve(self, runes: List[int]) -> int:
cnt=Counter(runes)
arr=sorted(cnt)
n=len(arr)
cur,ans=cnt[arr[0]],cnt[arr[0]]
for i in range(1,n):
if arr[i]-arr[i-1]>1:
ans=max(ans,cur)
cur=0
cur+=cnt[arr[i]]
ans=max(ans,cur)
return ans
首先使用计数器对 runes 中每个元素的出现次数进行统计，然后将这些魔力值排序。通过遍历这些排序后的魔力值，我们可以构建连续的符文块。如果两个连续的魔力值差大于 1，说明不能将它们放在一起，因此需要结束当前块的计数并开始新块的计数。通过这种方法，我们可以找到最大连续符文块的大小。
时间复杂度: O(n + m log m)
空间复杂度: O(m)
class Solution:
def runeReserve(self, runes: List[int]) -> int:
cnt = Counter(runes) # 计数每个符文出现的次数
arr = sorted(cnt) # 对有出现的符文值进行排序
n = len(arr) # 不同符文值的数量
cur, ans = cnt[arr[0]], cnt[arr[0]] # 初始化当前块和最大块的大小
for i in range(1, n):
if arr[i] - arr[i-1] > 1:
ans = max(ans, cur) # 结束当前块，比较并更新最大符文块的大小
cur = 0 # 重置当前块大小
cur += cnt[arr[i]] # 累加当前魔力值的出现次数到当前块
ans = max(ans, cur) # 最后一次更新最大符文块的大小
return ans # 返回最大符文块的大小
在构建连续符文块时，题解的目标是找出数组中连续的、数值上相邻的魔力值的最大集合。如果两个符文的魔力值之间的差大于1，意味着在这两个魔力值之间不存在其他魔力值，或者这些中间的魔力值在输入的符文列表中没有出现。由于题目要求的是连续的符文块，所以这些未出现的或数值不相邻的魔力值不能被用来形成连续的块，因此在这种情况下，我们必须结束当前块的计数并开始新的计数。
排序操作的时间复杂度通常是O(n log n)，其中n是需要排序的元素数量。在题解中，排序是对符文魔力值的唯一出现进行排序。如果输入的符文列表中包含大量的不同魔力值，那么排序操作将涉及大量的元素，从而增加计算时间。特别是当输入列表非常长且符文种类繁多时，排序可能成为算法中最耗时的部分。
这是因为当前块的结束是由于魔力值之间的断裂（即两个连续魔力值之间的差大于1）。当这种情况发生时，前一个块与当前考虑的魔力值之间没有连续性，因此必须开始一个全新的块。将当前块的计数重置为0是为了准备新的计数累计，开始统计下一个连续块。此时，累加下一个魔力值的计数是在之后的循环中进行的，因此初始化为0是确保计数正确开始的必要步骤。