use*_*235 5 algorithm set-theory graph-theory
我有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 的堆排序。通过从堆中拉出所有出现的相同值来处理联系，然后才决定要做什么。