能否在multiset（值可以重复）上以O(n)的时间复杂度执行查找第k个元素？
因为据我所知，快速选择的想法是使用某个中心点对输入进行分区。然后我有两个数组，我根据正在搜索的索引元素和这两个数组的大小来递归搜索，例如：
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））
那么对于multisets呢？假设我有一个数组：
4 5 6 7 7 7 4 3 2 1
我的中心点是6，我正在搜索第3个最大元素，在分区后，我收到了:
4 5 3 2 4 1 6 7 7 7
因此，如果我使用上面提出的方法，我将尝试在右侧子数组上递归执行，而很明显第三个最大值是5，它在左侧？
我想到的唯一解决方案是使用某些数据结构，例如BST、Set等，在O（nlogn）中过滤出重复项。然后使用O(n)快速选择。但是总体而言，这给了我非线性的方法，这可以在线性时间内完成吗？
我还有一个额外的问题，如果无法分配内存怎么办？我能做的就是使用本地整数+堆栈递归。这个问题可以在O(n)中解决吗？因为O(nlogn)可以通过排序+线性“遍历计数”来完成。
因为据我所知，快速选择的想法是使用某个中心点对输入进行分区。然后我有两个数组，我根据正在搜索的索引元素和这两个数组的大小来递归搜索，例如：
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））
那么对于multisets呢？假设我有一个数组：
4 5 6 7 7 7 4 3 2 1
我的中心点是6，我正在搜索第3个最大元素，在分区后，我收到了:
4 5 3 2 4 1 6 7 7 7
因此，如果我使用上面提出的方法，我将尝试在右侧子数组上递归执行，而很明显第三个最大值是5，它在左侧？
我想到的唯一解决方案是使用某些数据结构，例如BST、Set等，在O（nlogn）中过滤出重复项。然后使用O(n)快速选择。但是总体而言，这给了我非线性的方法，这可以在线性时间内完成吗？
我还有一个额外的问题，如果无法分配内存怎么办？我能做的就是使用本地整数+堆栈递归。这个问题可以在O(n)中解决吗？因为O(nlogn)可以通过排序+线性“遍历计数”来完成。