将序列分割成可形成非递减序列的片段的最小割数
我有N个整数，例如3、1、4、5、2、8、7。可能有一些重复的。我想把这个序列分成连续的子序列，这样我们就可以从它们形成非递减序列。如何计算最小切割次数？对于上面提到的例子，答案是6，因为我们可以将这个序列划分为{3}、{1}、{4,5}、{2}、{7}、{8}，然后形成{1,2,3,4,5,7,8}。最快的方法是什么？
有没有人知道假设某些数字可能相等时该怎么解呢？
共有1个答案
我会在值减少的点将数组切割成不减少的段，然后将这些段用作（单个）合并阶段的输入--就像排序-合并--在可能的情况下，在连接的情况下保持相同的段。当您必须从一个区段切换到另一个区段时，为切割创建额外的位置。
输出是排序的，因此这会产生足够的剪切来完成这项工作。在序列减少的地方产生切割，或者在由于原始序列跳过其他地方存在的数字而必须产生间隙的地方产生切割--因此没有所有这些切割的序列都不能重新排列成排序的顺序。
合并开销的最坏情况是初始序列正在减少。如果您使用一个堆来跟踪下一步要选择的序列，那么这将变成heapsort，成本为n log n。通过从堆中提取相同值的所有匹配项来处理绑定，然后再决定执行什么操作。
-
本文向大家介绍用Python将一个列表分割成小列表的实例讲解，包括了用Python将一个列表分割成小列表的实例讲解的使用技巧和注意事项，需要的朋友参考一下 方法一 方法二 效果 以上这篇用Python将一个列表分割成小列表的实例讲解就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持呐喊教程。
-
我们如何使用Pyspark2.4基于“/”之类的分隔符拆分sparkDataframe列 我的专栏包含： 谢谢
-
假设我们有一些不相交的递减序列： 我选择一些递减序列（例如按顺序,,,,的5个递减序列）并将它们级联（结果序列。 现在我想求S中最长递增子序列的长度，在上面的示例中:-> 预期时间复杂度小于O(S)。
-
我正在尝试使用shaka packager实现Mpeg DASH流媒体。要生成每个持续时间为5秒的分段，-segment_duration param帮助我实现这一点。 https://google.github.io/shaka-packager/html/documentation.html#chunking-选项 我可以从下面的链接中看到一段片段视频是如何呈现的 什么是碎片化mp4（fMP4
-
我已经设计了一个解决方案，可以使用一些测试用例，但是，对于许多我正在使用的算法是不正确的。 而不是寻求一个解决方案，我只是要求解释子序列是如何创建的，然后我将自己实现一个解决方案。 例如，输入： 6 6 问题陈述 在Quora上，我们有跟踪我们每天获得的支持投票数的聚合图。 当我们在特定大小的窗口上查看模式时，我们考虑了尽可能有效地跟踪趋势的方法，例如非递减和非递增子范围。 天数窗口定义为连续天数
-
我已经尝试了这里给出的许多解决方案，但我无法将这段代码拆分为多个表行。非常感谢！！ 更新：如果我的问题不清楚，很抱歉。我想喝5杯，然后开始新的一排，希望这能有所帮助。谢谢你的回答！ 有人能帮我吗？Minesh的代码很接近，但我仍然会出错，请参阅下面的评论。非常非常感谢！！