是否可以在多集（值可以重复）上在 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) 可以通过排序 + 线性“通过计数”来完成。