我有N个整数,例如3、1、4、5、2、8、7。可能有一些重复项。我想将此序列划分为连续的子序列,以便我们可以从中形成非递减序列。如何计算最小割数?对于上面提到的示例,答案是6,因为我们可以将此序列划分为{3},{1},{4、5},{2},{7},{8},然后形成{1、2 ,3、4、5、7、8}。最快的方法是什么?

假设某些数字相等,有人知道如何解决吗?

最佳答案

我将在值减小的点将数组切成非降序的段,然后将这些段用作(单个)合并阶段的输入(如在排序合并中),并在可能的情况下与同一段保持一致。关系的情况。当您必须从一个线段切换到另一线段时,请为剪切创建其他位置。

输出是经过排序的,因此这会产生足够的剪切量来完成任务。剪切在序列减少的点产生,或在必须创建缺口的点产生,因为原始序列跨越了其他位置存在的数字-因此没有所有这些剪切的序列都无法重新排列为排序的顺序。

合并开销的最坏情况是初始序列正在减少。如果使用堆来跟踪接下来要选择的序列,那么这将变成成本为n log n的堆排序。通过从堆中拉出所有具有相同值的事件来处理联系,然后才决定要做什么。

10-05 22:46
查看更多