寻找无序数组中第n个排序子数组所使用的算法是什么？

Question

我最近在面试中被问到这个问题，然后失败了，现在正在寻找答案。

1. 假设我有一个由n个整数组成的大数组，所有元素都不同。

2. 如果这个数组是有序的，我可以将它分割为x个更小的数组，每个数组的大小都为y，除了最后一个可能会比y小。然后我可以提取第n个子数组并返回其已排序的结果。

例如：数组 4 2 5 1 6 3。如果y=2，并且我想要第二个数组，则它应该是 3 4。

现在我的做法是简单地对数组进行排序并返回第n个子数组，这需要 O(n log n) 的时间复杂度。但是有人告诉我，有一种方法可以用 O(n + y log y) 的时间复杂度来解决这个问题。我搜索了互联网，但没有找到任何相关信息。有什么想法吗？

- Bene Tleilax

---

数组是从1开始以递增顺序排列的（只是被打乱了）（例如3, 1, 2, 4）？还是随机跳动的数字？（例如1, 12, 3, 5） - user3437460

从我的理解来看，它是随机数，唯一的前提是它们都不相同。 - Bene Tleilax

想一想快速排序的工作原理，然后思考如何使用它来确保数组元素101到150已排序。提示：这意味着当快速排序会对1到100个元素进行排序时，您不需要对其进行排序。 - gnasher729

Answer 1

您要寻找的算法是选择算法，它让您在线性时间内找到第k个次序统计量。该算法相当复杂，但标准C++库方便地提供了一个实现。

面试官想要的找到第k个排序间隔的算法如下：

• 以O（N）的时间找到b=(k-1)*y次序统计量
• 以O（N）的时间找到e=k*y次序统计量
• 在b和e之间将有y个数字。将它们存储在一个大小为y的单独数组中。这个操作需要O（N）
• 对大小为y的数组进行排序，成本为O（y * log₂y）。

总体成本为O（N+N+N+y * log₂y），即O（N+y * log₂y）。

- Sergey Kalinichenko

Answer 2

您可以结合使用 std::nth_element 和 std::sort 来实现此功能：

std::vector<int> vec = muchData();
// Fix those bound iterators as needed
auto lower = vec.begin() + k*y;
auto upper = lower + y;

// put right element at lower and partition vector by it
std::nth_element(vec.begin(), lower, vec.end());
// Same for upper, but don't mess up lower
std::nth_element(lower + 1, upper - 1, vec.end());
// Now sort the subarray
std::sort(lower, upper);

[lower, upper) 现在是长度为 y 的第 k 个排序子数组，平均复杂度达到了所需的要求。

在实际使用前需要检查像 y = 1 这样的特殊情况，但这是一般的想法。

- Baum mit Augen