Google面试题：验证数组是否为“好数组”（O(nlg²n)时间复杂度）

问题回顾 #

定义：若数组的每个子数组都至少包含一个出现次数为1的元素，则称该数组为“好数组”。要求设计确定性算法，以O(nlg²n)的时间复杂度验证数组是否为好数组。

分治法框架 #

• 拆分策略：将数组递归拆分为左右两个等长子数组
• 基准情况：长度为1的数组必然是好数组（唯一元素的出现次数为1）
• 递归验证：分别递归验证左右两个子数组是否为好数组

合并步骤的优化核心 #

直接合并时，若逐一检查所有跨越左右子数组的子数组（共O(n²)个），会导致时间复杂度失控。我们需要将合并步骤的时间复杂度优化至O(nlgn)，才能满足整体复杂度要求：

1. 此时算法的递推式为：T(n) = 2T(n/2) + O(nlgn)
2. 应用主定理（Master's Theorem），可推导出整体时间复杂度为 T(n) = O(nlg²n)

合并步骤的具体实现思路 #

针对跨越中点的子数组，我们可以通过以下方式高效验证：

• 预先统计左右子数组中每个元素的出现频率，存储在哈希表中
• 从数组中点开始，向左右两侧逐步扩展窗口，动态维护当前窗口内各元素的出现次数
• 利用有序结构（如平衡二叉搜索树）跟踪窗口内出现次数为1的元素，确保每次扩展窗口时能在O(lgn)时间内判断当前窗口是否符合要求
• 遍历所有可能的跨越中点的子数组，整体操作时间控制在O(nlgn)

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