非唯一排序数组中第k小的元素

Question

这可能是微软的面试题。给定一个有序数组，找出第k小的元素（忽略重复项）。
[编辑]：数组可能包含重复项（未指定）。
思考了很多次，但仍在质疑自己：还存在更好的解决方案吗？

方法1：

使用最大堆并插入前k个唯一元素[可以轻松检查]。然后进行堆化。
现在，当一个新元素比堆头小时，用这个新元素替换堆头并进行堆化。最后，如果堆的大小为k，则堆的头表示第k个最小元素，否则第k个最小元素不存在。
时间复杂度：O(NlogK)
空间复杂度：O(K)

方法2 [更好的方法]：

元素可能会重复。因此，通过与其前一个元素进行比较来检查唯一元素，并在到达k个唯一变量时停止。
时间复杂度：O(N)
空间复杂度：O(1)

方法3 [更好的方法(也许)]：

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

---

我在想是否存在O(logn)的解决方案？

- Green goblin

---

如果数组已排序，为什么不取第k个位置的元素呢？ - Sufian Latif

@KennyTM，这并不容易... 它可能会有重复项... - bragboy

KennyTM，FlopCoder：{1,1,1,1,2,2,3,4,5,6}。你们的算法在k = 3时返回了错误的值1。 - Nick

@Bragboy, ngmiceli：你们没有提及“唯一元素” :) 默认解释是包括重复元素，例如C++认为第3小的元素的正确答案是1。 - kennytm

在方法1中，输入的最后一个值就是所需的结果 - 而不是继续，给出有关前k个唯一元素[可以轻松检查]的详细信息。 - greybeard

Answer 1

这里有一个O(kLogN)的解决方案：

使用变形的二分查找来找到给定值的最后一次出现，

1. 获取第一个值 - O(1)。 2. 搜索该值的最后一次出现 - O(logN)，然后查看下一个元素以获取第二个值 - O(1)。 3. 重复此过程直到找到第k个值。

- mbeckish

---

这不比O(n)更好，它与O(k)相同。 - amitkarmakar

+1 - 这是一个很好的答案，当然也正是面试官所期望的。但需要注意的是，在某些_k_和_n_的值下，它比O(n)解决方案更慢。 - cheeken

@amit.codename13，一般来说是的，但还有另一种选项，对于各种输入都能更好地工作。 - unkulunkulu

考虑到 k 的值的上限为 N，我同意 @amit.codename13 的观点，即时间复杂度为 O(N logN)，最坏情况下仅比较列表中的值需要 O(N)。话虽如此，这是一道面试题目，他们希望你能提出这种非常规的解决方案。对于非常大的 N 和相对较小的 k，实际应用中会有性能提升。尽管如此，如果我真的雇用某人来完成这项任务（而不是测试他们的能力），如果他们没有在 O(N) 时间内扫描列表，我肯定会感到惊讶。 - acattle

@acattle - 如果这是一个真实项目，我会想知道为什么没有构建一个独立的唯一值索引，允许进行O(1)查找。 - mbeckish

Answer 2

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

最佳解决方案是O(n)时间和O(1)空间，就像你在第2步中描述的那样。我们可以证明这一点。

• 我们不能改进O(1)空间（至少不在O符号中）。
• 考虑一个运行时间小于O(n)的方法。这种方法必须不考虑数组中的每个元素。考虑一个被错过的元素。不知道这个元素是否是前一个或后一个值的重复项¹，而这些信息是需要断言哪个值对应于第k小的。

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

- cheeken

---

第二个陈述包含谬误。这种问题的唯一可能点就是我们应该努力跳过分析那些长度相等的序列。 - unkulunkulu

请检查我的第二条评论，你的陈述并没有显示出当所有跳过的元素都在相等的段中时的矛盾。我支持你的想法，即没有一般解决方案总是比O(n)更好（虽然有一种解决方案对于特定类别的输入来说确实比O(n)更好），我只是认为你的证明看起来是错误的。 - unkulunkulu

@unkulunkulu 我同意在那种情况下它并没有展示出矛盾（这就是为什么我在脚注中声明我忽略了那种情况）。如果有什么不清楚的地方请见谅。 - cheeken

是的，我没有理解关于脚注的部分，很抱歉。然后我也不明白你的陈述是什么意思。它说：“如果输入序列中不包含超过两个连续相等的元素，那么没有比O(n)更好的算法。” 我不明白它如何回答特定的问题，即关于一般情况甚至相反的问题。 - unkulunkulu

@unkulunkulu 总之，我的回答试图表达的是：“鉴于任意的输入，在速度方面没有比O(n)更好的算法。” - cheeken