找到每个 k 大小的子数组中的最大频率

Question

可能重复，但我找不到准确的。

这是涉及数据结构和算法的问题的一部分： 给定一个大小为 n 的数组，找到大小为 k 的每个窗口/子数组中所有元素的最大频率。

Ex1. a = {5,5,7,7,7,5} , k = 3
subarrays of size 3: 
{5,5,7} => freq[5] = 2, freq[7] = 1,  max frequency = 2 
{5,7,7} => freq[5] = 1, freq[7] = 2,  max frequency = 2
{7,7,7} => freq[7] = 3,               max frequency = 3
{7,7,5} => freq[5] = 1, freq[7] = 2,  max frequency = 2
answer array = {2,2,3,2}

Ex2: a = {5,5,6,5,5,6,6}, k = 5 , ans = {4, 3, 3}
Ex3  a = {1,2,3,4,5,6}  k = 2, ans = {1,1,1,1,1}

我的目标是在时间复杂度上最优地解决这个问题< O(N^2). Something like O(N * logN * logN). Not looking for O(N^2) Solution.

约束：N <= 10^5 , k <=N and a[i] <= 10^5

我的做法： 我尝试使用无序映射（用于存储每个子数组的频率）并使用多重集来解决频率更改后的最大值问题。

#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 * 6 * log(n) ) log(n) 。但我怀疑它是错误的，因为解决方案作为 TLE 失败了。

Answer 1

使用最大堆和计数映射。

根据元素的数量将元素放入堆中。

当元素进入/离开滑动窗口时调整计数并更新堆。

对于 n 个元素和大小为 k 的窗口，运行时间为 O(n log k)。

Ex2: a = {5,5,6,5,5,6,6}, k = 5 , ans = {4, 3, 3}

index map           comment
0:    {5=>1}
1:    {5=>2}
2:    {5=>2, 6=>1}
3:    {5=>3, 6=>1}
4:    {5=>4, 6=>1} # We've processed 5 elts; top of heap is 4 (from the 5)
5:    {5=>3, 6=>2} # We lose a 5 and gain a 6; top of heap is 3 (from the 5)
6:    {5=>2, 6=>3} # We lose another 5 and gain another 6; top of heap is 3 (from the 6)