arrays - 如何在不对数组进行排序的情况下在未排序的数组中找到第 k 个最小整数？

Question

所以我得到了一个包含 N 个不同整数的(未排序的)数组 A，我正在尝试实现一个分而治之的算法来找到数组中第 K 个最小的元素(K ≤ N)(即它将是如果 K=1，则整体最小)。该算法返回数组中第 K 个最小元素的值。在平均情况下，我需要它在 O(N) 时间内运行。谁能给我一些提示？

Answer 1

Sephy，我会非常仔细地完成这个过程。在用算法帮助人们时，你必须始终小心，因为，我怎么强调都不为过，解决算法问题对程序员来说就像举重对职业运动员一样。知道如何让自己进入像计算机一样的思维模式，是几年后你会得到报酬的事情。因此，如果只为您提供解决方案，您将成为每 6 个月从一个工作跳到另一个工作的人，而不是成为首席开发人员的人，或者独自离开一家成功的公司。

既然咆哮已经过去了......

传统上，我们认为算法会循环遍历数组一次，然后根据第一个结果以不同的方式循环遍历它，并重复直到满足某个条件，即 O(n^2)。满足此条件的是选择排序、插入排序和冒泡排序。

但这并不一定是。如果我们能够将数组适本地划分成段并证明这些段的大小，我们就可以将它保持在低阶。

而且，对于大多数分而治之的算法，我们可以从中间开始。

Let A be an array of size N with N distinct elements in it.

Let M be the element that resides at A[N/2]

Let A-large be an array of all elements greater than M.
Let A-small be an array of all elements less than M.

我们对 A-small 和 A-large 了解多少？它们大小一样吗？也许吧，但可能不是。

是size(A-small) > k ？或者是< k ？

如果size(A-small) == k - 1 ，这不会使 M 成为第 k 个最小的元素吗？

我们可以做些什么来为 k 创建一个新值并在这里进行一些递归吗？

我不会为你完成这个，因为应该有很多值得细细品味的东西。这些是您需要问自己的问题。 @templatetypedef 100% 走在正确的轨道上，这只是对其进行扩展。

如果您有更多问题，请问他们，但这里应该有足够的问题让您解决，而不会剥夺您的脑力锻炼。