algorithm - 获取第 k 组未排序的结果列表，每组具有任意数量的结果

Question

好吧，我有一大堆未知数据类型的未排序元素(显然，所有元素都是同一类型，我只是不能做出假设，因为它们可能是数字、字符串或任何类型的对象重载 < 和 > 运算符。我可以对这些对象做出的唯一假设是它们中没有两个是相同的，并且比较它们 (A < B) 应该让我知道如果它被排序，哪个应该首先出现。“最小的”应该是第一个。

我收到这个未排序的数组(类型为 std::vector，但老实说，它更像是一个算法问题，因此不需要特别的语言)，每个“组”的对象数 (groupSize)，以及发件人想要 (groupNumber)。

我应该返回一个包含 groupSize 元素的数组，如果请求的组是最后一个，则返回更少。 (示例:如果您要求第四组，groupSize 为 5 的 17 个结果将只返回其中两个。另外，第四组是组号 3，因为它是一个零索引数组)

例子:

接收到的数组:{1, 5, 8, 2, 19, -1, 6, 6.5, -14, 20}

收到的页面大小:3

收到页数:2

如果数组已排序，它将是:{-14, -1, 1, 2, 5, 6, 6.5, 8, 19, 20}

如果它被分成大小为 3 的组:{{-14, -1, 1}, {2, 5, 6}, {6.5, 8, 19}, {20}}

我必须返回第三组(0 索引数组中的 pageNumber 2):{6.5, 8, 19}

最大的问题是它需要快如闪电。我无法对数组进行排序，因为它必须比 O(n log n) 更快。

我已经尝试了几种方法，但永远无法达到 O(n log n)。

我知道我应该寻找一个不会填满所有其他组的解决方案，并跳过上面示例中显示的大部分步骤，以便在返回之前仅创建请求的组，但我想不出办法。

Answer 1

可以找到最小元素的值s使用标准 C++ 以线性时间在组中 std::nth_element函数(因为你知道它是排序数组中的索引)。可以找到最大的元素S在组中以同样的方式。之后，您需要线性遍历来找到所有元素 x这样 s <= x <= S并归还他们。总时间复杂度为O(n) .

注意:这个答案不是特定于 C++ 的。您只需要在线性时间内实现第 k 阶统计。