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

Question

我需要一个算法，给定一个数组和一个 int k，返回一个由 k 个“部分”数字组成的数组，并且：

• “零件”是有序的。这意味着如果一个数字在“部分”j 中，它小于“部分”i 中的每个数字，因为 i > j。

• “部分”中的元素不一定是有序的。

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

标签： arrayssortingksort

Answer 1

一种答案是简单地对数组进行排序，然后将其拆分为块，例如在伪代码中：

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));
}

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