Google 面试问题 - 检查数组的所有子数组是否至少有一个唯一元素

Question

我遇到了一个问题，我了解到这是一个谷歌面试问题。问题是：

如果每个子数组至少包含一个频率为 1 的元素，那么数组就是好的。

设计一个算法来验证数组是否具有 O(nlg^2(n)) 时间复杂度。我认为算法应该是确定性的，而不是随机的。

我想到了使用分而治之的方法： 我们将数组分成两半，并递归地检查它们是否良好。基本情况是当我们有一个大小为 1 的数组时，它始终是一个好的子数组。挑战在于如何组合两个子数组的结果并确定它们的串联在时间 o(n^2) 上是否也很好。这是因为我们在此步骤中有 O(n^2) 个子数组要检查。我们可以在 O(nlgn) 中完成组合步骤吗？如果是，我们得到递归：

T(n) = 2T(n/2)+O(nlgn)

然后，通过应用马斯特定理，我们可以得出结论：

T(n)=O(nlg^2n)

。

Answer 1

分而治之似乎是个好主意，但不要一分为二。相反，在数组中查找唯一元素，并将其用作划分点，同时从两个分区中排除该唯一元素。如果找到多个唯一元素，则划分更多的分区（以节省一些递归深度），使用所有唯一元素作为划分点。