java - 耐心排序并找到最长的递增子序列

标签 java algorithm sorting

我能够理解找到最长递增子序列的算法 HERE .但是也跟耐心排序有关。正如作者所说

Bonus: You have learnt Patience Sorting technique partially :).

我曾尝试从其他地方阅读耐心排序,但看不出它与最长递增子序列解决方案有何关系。 我正在尝试进行逆向工程,看看如何从最长递增子序列离开我们的点开始排序。 有人可以就此提出任何建议吗?此外,耐心排序的真正目的和优势是什么?

Here是与堆栈溢出相关的问题,它共享信息,但换句话说就是 - 如何使用耐心排序获得最长的递增子序列。

最佳答案

耐心排序只是另一种 O(n lg n) 排序算法(它实际上取决于实现)。如果您以前玩过单人纸牌游戏,那就有点类似了。该算法维护一个堆栈列表,每个堆栈都按降序(从尾到头)排序。数字是递增插入的。

要插入一个数字 x,找到最左边的堆栈,其顶部元素大于 x 并将 x 压入它。如果不存在这样的堆栈,则在末尾创建一个新堆栈并将 x 压入其上。请注意,我们插入数字的方式意味着堆栈的顶部元素按递增顺序排序,因此最长递增子序列的长度就是末尾堆的数量。

一旦所有数字都被插入并且堆就绪,我们将反复找到最小数字并将其写入输出。我们从中取出数字的堆栈现在必须插入一个新位置,以便再次对堆栈的顶部元素进行排序。这可以通过使用堆来存储堆栈来完成。

如果您简单地扫描顶部元素以找到最小值并且不使用花哨的数据结构,则算法采用 O(n sqrt(n)) 这对于小 n 来说还不错。

所以这对数字列表进行排序并为您提供 LIS 的长度(并且通过一些扩充为您提供 LIS)。

关于java - 耐心排序并找到最长的递增子序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28000601/

相关文章:

java - 自定义按钮 : properties change, 按钮应重新绘制

java - 从 onResponse 获取变量

java - 如何在 Java 中获取 Polybius 密码中单词的坐标?

algorithm - 如何以编程方式解决九九之谜?

c - 在 c 中扩展图形结构

java - 递归查找排序数组中第一次出现的数字

以优于 O(n^2) 的时间复杂度构造 count 数组

java - 集成到服务器的 PayPal API

algorithm - 如何重新排列不同种类的元素,使同类元素之间的距离最大?

在 CUDA 中对许多小数组进行排序