题目描述
给定一个整数数组 nums 和一个 正 整数 k 。
数组的 频率得分 是数组中 不同 值的 幂次 之和，并将和对 109 + 7 取模。
例如，数组 [5,4,5,7,4,4] 的频率得分为 (43 + 52 + 71) modulo (109 + 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 <= 1051 <= nums[i] <= 106
解法
方法一：哈希表 + 滑动窗口 + 快速幂
我们用哈希表 cnt 维护窗口大小为 $k$ 的元素及其出现的次数。
先算出初始窗口为 $k$ 的所有元素的分数。然后利用滑动窗口，每次加入一个元素，并移除最左边的元素，同时利用快速幂更新分数。
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 nums 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def maxFrequencyScore(self, nums: List[int], k: int) -> int:
mod = 10**9 + 7
cnt = Counter(nums[:k])
ans = cur = sum(pow(k, v, mod) for k, v in cnt.items()) % mod
i = k
while i < len(nums):
a, b = nums[i - k], nums[i]
if a != b:
cur += (b - 1) * pow(b, cnt[b], mod) if cnt[b] else b
cur -= (a - 1) * pow(a, cnt[a] - 1, mod) if cnt[a] > 1 else a
cur %= mod
cnt[b] += 1
cnt[a] -= 1
ans = max(ans, cur)
i += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 | class Solution {
private final int mod = (int) 1e9 + 7;
public int maxFrequencyScore(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < k; ++i) {
cnt.merge(nums[i], 1, Integer::sum);
}
long cur = 0;
for (var e : cnt.entrySet()) {
cur = (cur + qpow(e.getKey(), e.getValue())) % mod;
}
long ans = cur;
for (int i = k; i < nums.length; ++i) {
int a = nums[i - k];
int b = nums[i];
if (a != b) {
if (cnt.getOrDefault(b, 0) > 0) {
cur += (b - 1) * qpow(b, cnt.get(b)) % mod;
} else {
cur += b;
}
if (cnt.getOrDefault(a, 0) > 1) {
cur -= (a - 1) * qpow(a, cnt.get(a) - 1) % mod;
} else {
cur -= a;
}
cur = (cur + mod) % mod;
cnt.put(b, cnt.getOrDefault(b, 0) + 1);
cnt.put(a, cnt.getOrDefault(a, 0) - 1);
ans = Math.max(ans, cur);
}
}
return (int) ans;
}
private long qpow(long a, long n) {
long ans = 1;
for (; n > 0; n >>= 1) {
if ((n & 1) == 1) {
ans = ans * a % mod;
}
a = a * a % mod;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | class Solution {
public:
int maxFrequencyScore(vector<int>& nums, int k) {
using ll = long long;
const int mod = 1e9 + 7;
auto qpow = [&](ll a, ll n) {
ll ans = 1;
for (; n; n >>= 1) {
if (n & 1) {
ans = ans * a % mod;
}
a = a * a % mod;
}
return ans;
};
unordered_map<int, int> cnt;
for (int i = 0; i < k; ++i) {
cnt[nums[i]]++;
}
ll cur = 0;
for (auto& [k, v] : cnt) {
cur = (cur + qpow(k, v)) % mod;
}
ll ans = cur;
for (int i = k; i < nums.size(); ++i) {
int a = nums[i - k], b = nums[i];
if (a != b) {
cur += cnt[b] ? (b - 1) * qpow(b, cnt[b]) % mod : b;
cur -= cnt[a] > 1 ? (a - 1) * qpow(a, cnt[a] - 1) % mod : a;
cur = (cur + mod) % mod;
ans = max(ans, cur);
cnt[b]++;
cnt[a]--;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | func maxFrequencyScore(nums []int, k int) int {
cnt := map[int]int{}
for _, v := range nums[:k] {
cnt[v]++
}
cur := 0
const mod int = 1e9 + 7
qpow := func(a, n int) int {
ans := 1
for ; n > 0; n >>= 1 {
if n&1 == 1 {
ans = ans * a % mod
}
a = a * a % mod
}
return ans
}
for k, v := range cnt {
cur = (cur + qpow(k, v)) % mod
}
ans := cur
for i := k; i < len(nums); i++ {
a, b := nums[i-k], nums[i]
if a != b {
if cnt[b] > 0 {
cur += (b - 1) * qpow(b, cnt[b]) % mod
} else {
cur += b
}
if cnt[a] > 1 {
cur -= (a - 1) * qpow(a, cnt[a]-1) % mod
} else {
cur -= a
}
cur = (cur + mod) % mod
ans = max(ans, cur)
cnt[b]++
cnt[a]--
}
}
return ans
}
|