Question

2524. 子数组的最大频率分数

English Version

题目描述

给定一个整数数组 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 <= 105
• 1 <= nums[i] <= 106

解法

方法一：哈希表 + 滑动窗口 + 快速幂

我们用哈希表 cnt 维护窗口大小为 $k$ 的元素及其出现的次数。

先算出初始窗口为 $k$ 的所有元素的分数。然后利用滑动窗口，每次加入一个元素，并移除最左边的元素，同时利用快速幂更新分数。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 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 {
  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;
  }
}

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;
  }
};

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
}