好吧，我有一个未知数据类型的未排序元素的庞大数组（所有元素都是同一类型的，显然，我不能假设它们可能是数字、字符串或任何重载运算符的对象类型我能对这些物体做出的唯一假设是，它们中没有两个是相同的，比较它们（a我收到了这个未排序的数组（std：：vector类型，但老实说，它更多的是一个算法问题，因此不需要特别的语言）、每个“组”的对象数（groupSize）和发送者想要的组号（group number）。
我应该返回一个包含groupsize元素的数组，如果请求的组是最后一个，则返回小于或等于groupsize元素的数组。（示例：17个groupsize为5的结果，如果您请求第四个组，则只返回其中两个结果。另外，第四组是第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索引数组中的第2页）：{6.5，8，19}
最大的问题是它需要闪电般的速度我无法对数组排序，因为它必须比o（n logn）快。
我试过好几种方法，但都不可能成功。
我知道我应该寻找一个解决方案，它不能填满所有其他组，并且跳过上面示例中显示的相当大的一部分步骤，在返回请求的组之前只创建该组，但是我无法找到这样做的方法。
最佳答案
你可以在标准的C++s函数中找到组中最小元素std::nth_element的值（因为你知道它是排序数组中的索引）。您可以用同样的方法在组中找到最大的元素S之后，您需要一个线性过程来查找所有元素x以便s <= x <= S并返回它们。总时间复杂度O(n)。
注意：这个答案不是C++特定的。您只需要在线性时间内实现k阶统计量。
关于algorithm - 获取第k组未排序结果列表，每组任意数量的结果，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43006524/