问题标签 [quickselect]

我试图找到给定排序数组的最大 K 数。

例如：输入 -> [5, 12, 45, 32, 9, 20, 15] 输出 -> K = 3, [45, 32, 20]

到目前为止，我编写的代码返回了最大的 K 个元素，但它需要返回最大的 K 个数字。任何帮助，将不胜感激。

我尝试将Hoare 分区方案作为 Quickselect 算法的一部分来实现，但它似乎每次都能给我各种答案。

这是在findKthBest给定数组 ( data) 和其中的元素数 ( low = 0，high = 4如果有 5 个元素的情况下 ) 中找到数组中第 K 个最大数的函数：

该函数partition()有四个变量：

• data（一个列表，例如 5 个元素），
• l（列表中相关部分的起始位置，例如0）
• r（列表中相关部分的结束位置，也是放置枢轴的位置，例如 4）
• pivot（枢轴的值）

现在我每次都简单地得到各种结果，似乎递归效果不太好（有时它以达到最大递归错误结束），而不是每次都给出一个恒定的结果。我究竟做错了什么？

我有一个子数组 {8,9,7}。假设选择的枢轴是 8。在这个数组上运行 Quickselect 给了我一些问题。所以左指针从左边开始寻找大于 8 的元素找到 9。右指针从右边开始寻找小于 8 的元素找到 7。7 和 9 交换位置。{8,7,9} 现在左指针再次找到 9，右指针找到 7。但是现在它们已经相互交叉，所以我们不执行交换。相反，左指针与创建数组 {9,7,8} 的枢轴交换，但这并不好，因为较小的元素现在不在枢轴的左侧。那么我做错了什么？

我正在尝试实现此算法（来自此站点：https ://sarielhp.org/research/CG/applets/linear_prog/median.html ）。

FindKMedian( A, K ) // 返回 A 中第 K 个大小的数字。

1. 从 A = {a1, ..., an} 中随机选择一个数 a。
2. 将 n 个数分成两组：
   • S - 所有小于 a 的数
   • B - 所有大于 a 的数字
3. 如果 |S| = K-1 则 a 是所需的 K 中位数。返回一个
4. 如果 |S| < K-1 则 K 中值位于 B 中的某个位置。递归调用 FindKMedian( B, K - |S| - 1 )
5. 否则，递归调用 FindKMedian( S, K )。

在@mikake 回答之后，我在代码末尾使用参数调用函数时出错。

我希望数字 7 从 quickselect 的返回中出来（所以 quick_select(A, 5, 0, 9) 意味着“一旦子数组 A[0,...,5] 被排序或一次就找到 A[5] A[5,...,9] 已排序")。我可能没有明白这段代码的语义应该是什么。

谢谢

从https://en.wikipedia.org/wiki/Quickselect它说

“然而，不像在快速排序中那样递归到两边，快速选择只递归到一侧——它正在搜索的元素所在的一侧。这将平均复杂度从 O(n log n) 降低到 O(n)，与O(n^2) 的最坏情况。”

我不明白减少到只看一侧如何将平均复杂度降低到 O(n)？会不会更多 O(N/2 log N) 仍然是 O(N log N)。最坏的情况如何 O(n^2)

我的快速选择算法必须比seq.sort + seq(k). 我认为else if (low.length == 0) a(pivot)是错误的，我认为我的算法对于测试来说太慢了。

代码的一些结果：

我创建了一个SortableArray类的实例

然后我像这样调用quickselect实例来找到第一个最低值，第一个最低值实际上是第二低的值，因为它是零索引的。

然后我得到 undefined，这没有任何意义，因为 quickselect 方法包含一个 return 语句。

Linear time deterministic algorithm exists for selection. I read this link and the recurrence for a divide and conquer approach looks like: T(n) <= 12n/5 + T(n/5) + T(7n/10)

However, I don't understand why must it be T(7n/10). The link itself has mentioned that each half of the partition has size (3n/10), so the algorithm recurses on (6n/10). Even if we include the 5 elements from the group of the median of medians, the recursion is on (6n/10+5). I do understand that 7n/10 is a valid upper bound on the size of the recursion, but isn't it too weak an upper bound here?

我一直在尝试理解快速选择算法，并且我发现了最坏情况运行时间复杂度的两个不同值。

例如，该网站声称最坏情况的时间复杂度是 Θ(n^2)，而GeeksforGeeks声称它是 O(n^2)。

有人可以帮我理解哪一个是正确的，为什么会这样？

I need an algorithm which can find the median of a singly linked list in linear time complexity O(n) and constant space complexity O(1).

EDIT: The singly linked list is a C-style singly linked list. No stl allowed (no container, no functions, everything stl is forbidden, e.g no std::forward_list). Not allowed to move the numbers in any other container (like an array). It's acceptable to have a space complexity of O(logn) as this will be actually even under 100 for my lists. Also I am not allowed to use the STL functions like the nth_element

Basically I have linked list with like 3 * 10^6 elements and I need to get the median in 3 seconds, so I can't use a sorting algoritm to sort the list (that will be O(nlogn) and will take something like 10-14 seconds maybe).

I've done some search online and I've found that it's posibile to find the median of an std::vector in O(n) and O(1) space compleity with quickselect (the worst case is in O(n^2), but it is rare), example: https://www.geeksforgeeks.org/quickselect-a-simple-iterative-implementation/

But I can't find any algoritm that does this for a linked list. The issue is that I can use the array index to randomly acces the vectorIf I want to modify that algoritm the complexity will be much bigger, because. For example when I change the pivotindex to the left I actually need to traverse the list to get that new element and go further (this will get me at least O(kn) with a big k for my list, even aproching O(n^2)...).

EDIT 2:

I know I have too many variables but I've been testing different stuff and I am still working on my code... My current code:

Do you have any sugestion on how to adapt quickselect to a singly listed link or other algoritm that would work for my problem ?