将数组排序为未排序元素的k个排序部分

Question

我需要一个算法，在给定一个数组和一个int k的情况下，返回一个由k个数字组成的数组：

• 已订购"零件"。这意味着，如果一个数字在"部分"j中，对于i>j，它小于"部分"i中的每个数字。

• "零件"中的元素不一定是有序的。

仅供参考，这不是一个k排序的问题！我找不到任何关于它的信息。每次搜索都只返回k排序的算法和讨论。

Answer 1

一个答案是简单地对数组进行排序，然后将其拆分为块，例如在psuedocode:中

sorted_arr = sorted(arr)
new_arr = []
arr_len = size(arr)
chunk_len = max(1, floor(arr_len / k))
for (i = 0; i < arr_len; i += chunk_size) {
new_arr.push(sorted_arr.slice(i, i + chunk_len));
}

但我猜你正在寻找一个比实际先排序数组然后分块更快的解决方案。