2524：子数组的最大频率分数（★★）

Ian

2023-01-03 约 348 字预计阅读 1 分钟次阅读

力扣第 2524 题

题目

给定一个整数数组 nums 和一个正整数 k 。

数组的 频率得分 是数组中不同值的幂次之和，并将和对 10⁹ + 7 取模。

例如，数组 [5,4,5,7,4,4] 的频率得分为 (4³ + 5² + 7¹) modulo (10⁹ + 7) = 96 。

返回 nums 中长度为 k 的 子数组 的最大频率得分。你需要返回取模后的最大值，而不是实际值。

子数组 是一个数组的连续部分。

示例 1 ：

输入：nums = [1,1,1,2,1,2], k = 3
输出：5
解释：子数组 [2,1,2] 的频率分数等于 5。可以证明这是我们可以获得的最大频率分数。

示例 2 ：

输入：nums = [1,1,1,1,1,1], k = 4
输出：1
解释：所有长度为 4 的子数组的频率得分都等于 1。

提示：

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

分析

哈希表维护每个数的频率，滑动窗口维护得分即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        mod = 10**9+7
        ct = defaultdict(int)
        res,s = 0,0
        for i,x in enumerate(nums):
            ct[x] += 1
            s += pow(x,ct[x],mod)-(pow(x,ct[x]-1,mod) if ct[x]>1 else 0)
            if i>=k:
                y = nums[i-k]
                s -= pow(y,ct[y],mod)-(pow(y,ct[y]-1,mod) if ct[y]>1 else 0)
                ct[y] -= 1
            s %= mod
            if i>=k-1:
                res = max(res,s)
        return res

463 ms

目录

2524：子数组的最大频率分数（★★）

题目

分析

解答