如何求解数组中所有长度为k的连续子数组的众数，可优化到O(1)吗？

问题梳理 #

给定长度为n的数组与参数k，需要输出数组中所有长度为k的连续子数组的众数。
参考示例：

输入：arr = [1,2,2,6,6,1,1,7], k = 3
输出：[2,2,6,6,1,1]

你当前使用哈希表+TreeMap的方案时间复杂度为O(nlogn)，接下来先澄清时间复杂度的认知误区，再给出更优的实现方案。 #

时间复杂度误区澄清 #

不存在整体O(1)的解法，因为必须遍历所有n个元素，处理共n-k+1个窗口，整体时间复杂度下界为O(n)。你提到的O(1)应该是指单步窗口滑动的均摊操作复杂度为O(1)，最终整体达到O(n)的线性时间复杂度，这个需求是可以实现的。 #

O(n)时间复杂度实现方案 #

我们可以用频率桶+最大频率标记替换TreeMap，将单步操作的时间复杂度从O(logk)降到均摊O(1)，具体实现逻辑如下：

• 维护count哈希表：存储当前窗口内每个数值对应的出现频率
• 维护freq集合数组：下标为频率值，对应位置存储所有出现频率等于该下标的数值集合
• 维护max_freq变量：记录当前窗口内的最大频率值

窗口滑动操作逻辑 #

1. 窗口右边界右移，加入新元素x：
   • 若count[x] > 0，先将x从freq[count[x]]的集合中移除
   • count[x] += 1
   • 将x加入freq[count[x]]的集合
   • 如果count[x] > max_freq，更新max_freq = count[x]
2. 当窗口长度超过k时，窗口左边界右移，移除旧元素y：
   • 将y从freq[count[y]]的集合中移除
   • count[y] -= 1
   • 若count[y] > 0，将y加入freq[count[y]]的集合
   • 如果freq[max_freq]为空，说明原最高频率的元素已全部移出窗口，max_freq -= 1
3. 当窗口长度等于k时，freq[max_freq]中的元素即为当前窗口的众数（若存在多个众数可按题目要求选择返回值）

该方案所有操作的均摊时间复杂度为O(1)，整体时间复杂度为O(n)，空间复杂度为O(n)。如果k远小于n，还可以进一步优化空间占用到O(k)。 #

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