是否可以在multiset(值可以重复)上执行O(n)中的第k个元素的搜索?
因为根据我对快速选择的理解我必须用某个主元来划分输入。然后我有两个数组，我选择递归搜索取决于我要搜索的索引元素+两个数组的大小例如:
1 7 8 5 3 2 4
假设pivot = 4，我在搜索第二大元素。在分割之后，我可能得到像
这样的顺序1 3 2 4 7 8 5
因为右子数组由3个元素组成，我仍然会尝试在右数组中找到第二大元素，如果我是正确的?
但是如果我把8作为一个枢轴，我可能会得到像
这样的东西1 3 2 7 5 4 8
，因此我将尝试在左表中找到最大的元素(可能是线性的，但通常我会取左子数组并搜索元素-(|右子数组大小| + 1))
但是多集呢?比如我有一个数组:
4 5 6 7 7 7 7 4 3 2 1
和我的枢轴是6搜索第三大元素，分区后我收到:
4 5 3 2 4 1 6 7 7 7
那么如果我使用上面的方法，我将尝试对右子数组执行递归，而第三大的值显然是5，在左边?
我想到的唯一解决方案是使用一些数据结构，如BST, Set等O(nlogn)过滤掉重复。然后使用O(n)快速选择。然而总的来说，它会给我非线性的方法，这可以线性地完成吗?
我还有一个额外的问题，如果不能分配内存怎么办?我能做的就是使用局部int +堆栈递归。这个问题可以在O(n)内解决?因为O(nlogn)可以通过排序+线性"遍历计数"来完成。
我认为这取决于你对"第k大元素"的解释。如果你所说的"第k大元素"是指"在数组中排序后位于第k位的元素"，那么快速选择将不需要修改就可以工作。
另一方面，如果您指的是"数组中第k大的不同值"，那么您是正确的，未修改的快速选择将不能正常工作，如您的示例所示。但是，您可以通过将所有元素添加到散列表中，然后遍历散列表以获得每个不同值的一个副本，从而修改算法，使其在预期的O(n)时间内工作。从那里，您可以在生成的数组上使用普通的快速选择算法，这将需要总共O(n)的预期时间。
希望这对你有帮助!