文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
恩，这个学期开算法课，跟着进度写写代码就好。这周讲分治，说到了求N个数中第K小(大)数的问题，写写看。
分治算法的复杂度是O(n)，用到了快速排序的思路：先选取一个参考数进行一次快排，拿升序来说的话，快排之后左边所有数<参考数，右边所有数>参考数，然后根据左右部分各自包含元素的个数，计算要求的元素在哪个区间内(要求的元素或是左区间中的第k小数，或是右区间中第[k-j]小数，j为左区间的长度)，然后递归求解。
本来pku 2104和pku 2761都是求第K小数的题，无奈用这个算法TLE，只能用后面的划分树或是其他复杂度更低的算法来做，以后再说吧。我这里只贴用这个算法做的，虽然交上去会TLE...
文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
刚才用O(n^2)的DP算法做了最长上升子序列，具体见POJ2533解题报告。后来在网上看到说LIS问题有O(nlogn)的算法，于是拿来小研究了一下。
这个算法其实已经不是DP了，有点像贪心。至于复杂度降低其实是因为这个算法里面用到了二分搜索。本来有N个数要处理是O(n)，每次计算要查找N次还是O(n)，一共就是O(n^2)；现在搜索换成了O(logn)的二分搜索，总的复杂度就变为O(nlogn)了。
这个算法的具体操作如下(by RyanWang):
开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。 最长序列长度即为栈的大小top。
这也是很好理解的，对于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y]，此时的最长序列长度没有改变但序列Q的''潜力''增大了。
举例：原序列为1，5，8，3，6，7
栈为1，5，8，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。
用该算法完成POJ2533的具体代码如下:
最新评论