abc*_*abc 5 algorithm selection multiset quickselect
是否可以在O（n）上对多集执行第k个元素的搜索（值可以重复）？
因为据我了解的快速选择的想法，我必须使用一些支点来划分输入。然后，我有2个数组，我选择进行递归搜索取决于我要搜索的索引元素+两个数组的大小分别是多少：
1 7 8 5 3 2 4
假设数据透视为4，我正在搜索第二大元素。所以分区后我可能会得到像
1 3 2 4 7 8 5
因为正确的子数组由3个元素组成，如果我是正确的话，我仍然会尝试在正确的数组中找到第二大的数组？
但是，如果我以8为支点，我可能会得到类似
1 3 2 7 5 4 8
因此，我将尝试在左侧表格中找到最大的元素（适当地通过线性查找，但一般而言，我将采用左侧子数组并搜索元素-（|右侧子数组大小| + 1））
但是多集呢？假设我有数组：
4 5 6 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）快速选择。但是总的来说，它会给我非线性方法，这可以线性吗？
我还有一个额外的问题，如果无法完成分配内存该怎么办？我所能做的就是只使用局部整数+堆栈递归。这个问题可以在O（n）中解决吗？因为O（nlogn）可以通过排序+线性“通过计数”来完成。
我认为这取决于你对“第k大元素”的解释。如果“第 k 个最大元素”的意思是“如果已排序，则该元素将位于数组中的位置 k”，那么快速选择将无需修改即可工作。
另一方面，如果您的意思是“数组中不同值的第 k 个最大”，那么您是正确的，未经修改的快速选择将无法正常工作，如您的示例所示。但是，您可以修改算法，使其在预期的 O(n) 时间内工作，方法是将所有元素添加到哈希表中，然后迭代哈希表以获取每个不同值的一个副本。从那里，您可以在生成的数组上使用正常的快速选择算法，这总共需要 O(n) 时间。
希望这可以帮助！