You are given an integer array nums
and a positive integer k
.
The frequency score of an array is the sum of the distinct values in the array raised to the power of their frequencies, taking the sum modulo 109 + 7
.
- For example, the frequency score of the array
[5,4,5,7,4,4]
is(43 + 52 + 71) modulo (109 + 7) = 96
.
Return the maximum frequency score of a subarray of size k
in nums
. You should maximize the value under the modulo and not the actual value.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,1,1,2,1,2], k = 3 Output: 5 Explanation: The subarray [2,1,2] has a frequency score equal to 5. It can be shown that it is the maximum frequency score we can have.
Example 2:
Input: nums = [1,1,1,1,1,1], k = 4 Output: 1 Explanation: All the subarrays of length 4 have a frequency score equal to 1.
Constraints:
1 <= k <= nums.length <= 105
1 <= nums[i] <= 106
方法一:哈希表 + 滑动窗口 + 快速幂
我们用哈希表 cnt
维护窗口大小为
先算出初始窗口为
时间复杂度 nums
的长度。
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
class Solution {
public int maxFrequencyScore(int[] nums, int k) {
final int mod = (int) 1e9 + 7;
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < k; ++i) {
cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
}
long cur = 0;
for (var e : cnt.entrySet()) {
cur = (cur + qmi(e.getKey(), e.getValue(), mod)) % 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) * qmi(b, cnt.get(b), mod) % mod;
} else {
cur += b;
}
if (cnt.getOrDefault(a, 0) > 1) {
cur -= (a - 1) * qmi(a, cnt.get(a) - 1, mod) % 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;
}
long qmi(long a, long k, long p) {
long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % p;
}
k >>= 1;
a = a * a % p;
}
return res;
}
}
class Solution {
public:
int maxFrequencyScore(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (int i = 0; i < k; ++i) {
cnt[nums[i]]++;
}
long cur = 0;
const int mod = 1e9 + 7;
for (auto& [k, v] : cnt) {
cur = (cur + qmi(k, v, mod)) % mod;
}
long 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) * qmi(b, cnt[b], mod) % mod : b;
cur -= cnt[a] > 1 ? (a - 1) * qmi(a, cnt[a] - 1, mod) % mod : a;
cur = (cur + mod) % mod;
ans = max(ans, cur);
cnt[b]++;
cnt[a]--;
}
}
return ans;
}
long qmi(long a, long k, long p) {
long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % p;
}
k >>= 1;
a = a * a % p;
}
return res;
}
};
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
for k, v := range cnt {
cur = (cur + qmi(k, v, mod)) % 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) * qmi(b, cnt[b], mod) % mod
} else {
cur += b
}
if cnt[a] > 1 {
cur -= (a - 1) * qmi(a, cnt[a]-1, mod) % mod
} else {
cur -= a
}
cur = (cur + mod) % mod
ans = max(ans, cur)
cnt[b]++
cnt[a]--
}
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func qmi(a, k, p int) int {
res := 1
for k != 0 {
if k&1 == 1 {
res = res * a % p
}
k >>= 1
a = a * a % p
}
return res
}