获取第 k 组未排序的结果列表，每组具有任意数量的结果
Get kth group of unsorted result list with arbitrary number of results per group
好吧，我有一大堆未知数据类型的未排序元素（所有元素都是同一类型，显然，我无法做出假设，因为它们可能是数字、字符串或任何类型的重载 < 和 > 运算符的对象。关于这些对象，我可以做的唯一假设是它们中没有两个是相同的，并且比较它们 (A < B) 应该让我知道如果它被排序，哪个应该首先出现。 "smallest" 应该是第一个。
我收到了这个未排序的数组（类型 std::vector，但老实说，它更像是一个算法问题，因此不需要特别的语言），每个 "group"（groupSize）的对象数量，以及发件人想要的组号 (groupNumber).
我应该 return 一个包含 groupSize 元素的数组，或者如果请求的组是最后一个，则更少。 （示例：如果您要求第四组，groupSize 为 5 的 17 个结果只会 return 其中两个。此外，第四组是组号 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}}
我必须 return 第三组（0 索引数组中的 pageNumber 2）：{6.5, 8, 19}
最大的问题是它需要快如闪电。我无法对数组进行排序，因为它必须比 O(n log n) 更快。
我尝试了几种方法，但始终无法在 O(n log n) 下完成。
我知道我应该寻找一个不会填满所有其他组的解决方案，并跳过上面示例中显示的大部分步骤，以便在之前仅创建请求的组return正在处理，但我想不出办法。
您可以使用标准 C++ std::nth_element 函数在线性时间内找到组中最小元素 s 的值（因为您知道它在排序数组中的索引）。同样的方法可以找到组中最大的元素S。之后，您需要一个线性传递来找到所有元素 x 使得 s <= x <= S 和 return 它们。总时间复杂度为O(n)。
注意：这个答案不是特定于 C++ 的。您只需要在线性时间内实现第 k 阶统计。
好吧，我有一大堆未知数据类型的未排序元素（所有元素都是同一类型，显然，我无法做出假设，因为它们可能是数字、字符串或任何类型的重载 < 和 > 运算符的对象。关于这些对象，我可以做的唯一假设是它们中没有两个是相同的，并且比较它们 (A < B) 应该让我知道如果它被排序，哪个应该首先出现。 "smallest" 应该是第一个。
我收到了这个未排序的数组（类型 std::vector，但老实说，它更像是一个算法问题，因此不需要特别的语言），每个 "group"（groupSize）的对象数量，以及发件人想要的组号 (groupNumber).
我应该 return 一个包含 groupSize 元素的数组，或者如果请求的组是最后一个，则更少。 （示例：如果您要求第四组，groupSize 为 5 的 17 个结果只会 return 其中两个。此外，第四组是组号 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}}
我必须 return 第三组（0 索引数组中的 pageNumber 2）：{6.5, 8, 19}
最大的问题是它需要快如闪电。我无法对数组进行排序，因为它必须比 O(n log n) 更快。
我尝试了几种方法，但始终无法在 O(n log n) 下完成。
我知道我应该寻找一个不会填满所有其他组的解决方案，并跳过上面示例中显示的大部分步骤，以便在之前仅创建请求的组return正在处理，但我想不出办法。
您可以使用标准 C++ std::nth_element 函数在线性时间内找到组中最小元素 s 的值（因为您知道它在排序数组中的索引）。同样的方法可以找到组中最大的元素S。之后，您需要一个线性传递来找到所有元素 x 使得 s <= x <= S 和 return 它们。总时间复杂度为O(n)。
注意：这个答案不是特定于 C++ 的。您只需要在线性时间内实现第 k 阶统计。