9

这可能是一个微软面试问题。

从排序数组中找到第 k 个最小的元素（忽略重复项）。
[编辑]：数组可能包含重复项（未指定）。

想了很多次，但还是在问自己：还有更好的解决方案吗？

方法一：

取一个最大堆并插入前 k 个唯一元素[可以很容易地检查]。堆化堆。
现在，当一个新元素小于堆头时，用这个新元素替换堆头。最后，如果堆的大小为 k，则堆头指示第 k 个最小元素，否则第 k 个最小元素不存在。

时间复杂度：O(NlogK)
空间复杂度：O(K)

方法2[更好的方法]：

元素可以正确复制。因此，通过与之前的元素进行比较来检查唯一元素，如果到目前为止发现的唯一变量计数为 k，则停止。
时间复杂度：O(N)
空间复杂度：O(1)

方法3[更好的方法（可能）]：

也可以使用快速排序分区算法的修改版本。但可能会导致最坏的情况，因为数组已经排序。
这里出现了两个问题：
1.如果数组包含重复项，它是否有效？
2.它会比我的第二个方法更好吗？

我想知道是否存在任何 O(logn) 解决方案？

4

2 回答 2

8

这是一个 O(kLogN) 解决方案：

使用二分搜索的变体来查找给定值的最后一次出现，

  1. 获取第一个值 - O(1)。
  2. 搜索该值的最后一次出现 O(logN)，然后查看下一个元素以获得第二个值 - O(1)。
  3. 重复直到找到第 k 个值。
于 2012-06-21T17:46:37.070 回答
5

第k个最小元素似乎有两种不同的解释。我假设它的意思是“第k个最小的元素，忽略重复项”。

最好的解决方案是 O(n) 时间和 O(1) 空间，正如您在方法 2 中描述的那样。我们可以证明这一点。

  • 我们无法改进 O(1) 空间（至少不是在 O 表示法中）。
  • 考虑一种运行时间小于 O(n) 的方法。这种方法不能考虑数组中的每个元素。考虑一个这样的遗漏元素。不知道该元素是否是它之前或之后的值的副本¹，并且需要此信息来断言数组中的哪个值对应于第k个最小值。

¹ 在两个不相邻的数组元素具有相同值的特殊情况下，可以推断出排序数组的任意长子序列的值：所有中间元素必须共享该值。但这不是一个典型的案例，所以我忽略了它。

于 2012-06-21T17:41:17.430 回答