求每个k长度子数组的最大频率 最优算法求解问询

问题描述 #

给定大小为n的数组，找出每个k大小子数组中所有元素的最大频率。

示例 #

• Ex1: a = {5,5,7,7,7,5}, k = 3
  子数组分析：

  {5,5,7} => freq[5]=2，freq[7]=1，最大频率=2
  {5,7,7} => freq[5]=1，freq[7]=2，最大频率=2
  {7,7,7} => freq[7]=3，最大频率=3
  {7,7,5} => freq[5]=1，freq[7]=2，最大频率=2
  结果数组：{2,2,3,2}

• Ex2: a = {5,5,6,5,5,6,6}, k = 5，结果：{4,3,3}

• Ex3: a = {1,2,3,4,5,6}, k = 2，结果：{1,1,1,1,1}

约束条件 #

• N ≤ 10^5
• k ≤ N
• a[i] ≤ 10^5

目标 #

寻找时间复杂度**严格小于O(N²)**的最优解法（比如O(N logN)或O(N logN logN)），拒绝O(N²)解法。

当前实现思路与代码 #

采用unordered_map存储子数组元素频率，用multiset维护频率集合以快速获取最大值。代码如下：

#include <bits/stdc++.h>
using namespace std;

int check(vector<int> &nums, int k)
{
    int n=nums.size();
    unordered_map<int,int> mp;
    multiset<int> st;
    
    for(int i=0;i<n;i++)
    {

        if( i >= k )
        {
            int idx_b = i-k;
             auto itr2 = st.find(mp[nums[idx_b]]);
            if ( itr2!=st.end() ) st.erase(itr2);
            mp[nums[idx_b]]--;
            st.insert(mp[nums[idx_b]]);
        }

        int curr = mp[nums[i]]; 
        mp[nums[i]]++;

        auto itr1 = st.find(curr);
        if(itr1!=st.end())st.erase(itr1);
        st.insert(curr+1);

        auto mx = st.rbegin();
        if(i>=k-1 )
        {
            cout<<*mx<<endl;
        }
    }
    return 0;
    
}

int main()
{
    vector<int> a { 5,5,6,6,6,7};
    check(a,3);
    
}

遇到的问题 #

原以为时间复杂度是O(N * logN)（每个元素对应最多6次logN级别的操作：find/erase/insert），但提交后出现超时（TLE），需要优化建议或正确解法。

优化建议与解法 #

问题根源

当前解法中，multiset的find操作是O(logM)（M为不同频率的数量），且unordered_map的哈希冲突会增加实际耗时；另外，每次修改频率时都要在multiset中删除旧值、插入新值，频繁操作累积后对1e5量级的数据来说效率不足。

优化方案：用频率计数数组替代multiset

维护一个数组freq_count，其中freq_count[f]表示当前窗口中频率为f的元素数量，同时维护当前窗口的最大频率max_freq。这样可以避免multiset的频繁查找与修改，将时间复杂度降到O(N)（平均情况）。

具体步骤：

1. 初始化unordered_map<int, int> elem_freq记录每个元素的当前频率，vector<int> freq_count(n+1, 0)（最大频率不超过k≤n），int max_freq = 0。
2. 滑动窗口处理：
   • 加入当前元素：先减少旧频率的计数，更新元素频率后增加新频率的计数，同步更新max_freq。
   • 窗口超过k时，移除左端元素：减少该元素旧频率的计数，若旧频率等于当前max_freq且无元素再拥有该频率，则max_freq递减；随后更新元素频率并增加新频率的计数。
   • 窗口大小达到k时，记录max_freq到结果中。

优化后的代码

#include <bits/stdc++.h>
using namespace std;

vector<int> maxFrequencyInSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;
    unordered_map<int, int> elem_freq;
    vector<int> freq_count(n + 1, 0); // freq_count[f] = 频率为f的元素数量
    int max_freq = 0;

    for (int i = 0; i < n; ++i) {
        // 加入当前元素到窗口
        int num = nums[i];
        if (elem_freq[num] > 0) {
            freq_count[elem_freq[num]]--;
        }
        elem_freq[num]++;
        freq_count[elem_freq[num]]++;
        max_freq = max(max_freq, elem_freq[num]);

        // 窗口超过大小k时，移除左端元素
        if (i >= k) {
            int left_num = nums[i - k];
            freq_count[elem_freq[left_num]]--;
            // 若当前最大频率来自该元素且已无元素拥有此频率，递减max_freq
            if (elem_freq[left_num] == max_freq && freq_count[max_freq] == 0) {
                max_freq--;
            }
            elem_freq[left_num]--;
            freq_count[elem_freq[left_num]]++;
        }

        // 窗口有效时收集结果
        if (i >= k - 1) {
            result.push_back(max_freq);
        }
    }

    return result;
}

int main() {
    vector<int> a = {5,5,6,6,6,7};
    vector<int> res = maxFrequencyInSlidingWindow(a, 3);
    for (int num : res) {
        cout << num << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N)（平均情况），每个元素的加入和移除操作都是O(1)的哈希表操作，max_freq的递减总次数不超过N次。
• 空间复杂度：O(N)，用于存储elem_freq和freq_count。

内容的提问来源于stack exchange，提问作者Ashutosh Rana