给定一个未排序数组, 找出其中最长的等差数列

发布时间:2016-12-6 13:51:26 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"给定一个未排序数组, 找出其中最长的等差数列",主要涉及到给定一个未排序数组, 找出其中最长的等差数列方面的内容,对于给定一个未排序数组, 找出其中最长的等差数列感兴趣的同学可以参考一下。

转载请注明来自souldak,微博:@evagle 题目如题所诉:其实就是前面那篇leetcode 最长连续序列 longest consecutive sequence 的升级版 leetcode上的题目是要求等差为1,即连续序列,而现在把等差为1的限制条件去掉,找最长的等差数列,做法和复杂度却升级了。 现在给出一个O(n^2)的算法: 算法思路: 先排序,O(NlogN) 从后往前,对于a[i],令 j=i+1~n-1 map[pair(a[i],a[j]-a[i])] = max(map[pair(a[j]-,a[j]-[a[i])] , 1) + 1  其中pair(a,b)表示以a为首项,b为等差的等差数列的最长的长度 从a[n-1]一直算到a[0],所有的pair(a[k],b)都算出来了,现在只要找出其中最大的即可。 按着这个思路,代码实现也比较简单,就不上代码了。

上一篇:Git详解之六:Git工具
下一篇:改善C++ 程序的150个建议学习之建议14:小心typedef使用中的陷阱

相关文章

相关评论