c++ - 修改排序数组还是每次都对数组排序？

Question

问题:给定一个大小为 N 的数组，打印具有连续元素的大小为 K 的已排序子集。

N = 10, K = 4 
8 4 7 5 1 10 3 9 2 6
Output:
4 5 7 8, 1 4 5 7, 1 5 7 10, 1 3 5 10, ...

方法 1:对所有子集进行排序并打印。

复杂性分析:

复制 K 个元素:O((N - K + 1) * (K))//子集数量 * 子集大小

排序子集:使用STL ，对子集进行排序的最坏情况时间是 O(K log K)。

因此，O((N - K + 1) * (K) + (N - K + 1) * (K log K))

方法二:从输出序列来看，连续的子集相差2个元素。因此对于第二个子集，删除第一个元素，在正确的位置插入第K+1个元素。

复杂性分析:

创建第一个子集:K

删除和插入 - 线性搜索(应该优化这个!):K

因此，O(K + (N - K + 1) * (K))

我想知道第二种方法是否更快？有明显的收获吗？不使用STL实现值得吗？这可以进一步改进吗？还有其他方法吗？以及对 STL 容器实现的任何建议。

Answer 1

是否允许重复？

如果不允许重复，使用std::set , 否则使用 std::multiset . set 和 multiset 将使您的元素始终保持有序，并且每次插入都会出现在正确、​​有序的位置。您不必担心何时对它们进行排序。

在插入期间对所有元素进行排序实际上更便宜，因为当您必须搜索时，您不必与所有元素进行比较，而只需与它们的一个子集进行比较。