最长递增子序列
发布时间
阅读量：
阅读量
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
输入: [1,3,6,7,9,4,10,5,6]
输出: 6
这一题，我刚开始得思路就是暴力法：
创建一个数组，用来记录它此时所在得最长长度，这个最长长度就是由从前一位开始，向后遍历，计算最长的长度；如果数值相等就不需要在遍历了；
很明显这是一个O(n^2)的算法
code:
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.empty())
return 0;
int size=nums.size();
vector<int> count(size,1);
int j=0;
int Max=1;
int temp=1;
for(int i=0;i<size;i++)
{
j=i;
temp=1;
while(--j>=0)
{
if(nums[i]>nums[j])
{
Max=max(count[j]+1,Max);
temp=max(temp,count[j]+1);
}
else if(nums[i]==nums[j])
{
count[i]=count[j];
break;
}
}
count[i]=temp;
}
return Max;
}
};
下面给出O(nlgn)的算法：
它用一个数组array 来记录，数组的索引k 表示此时最长长度k+1 的最小值 为array[k];
比如：[1,3,6,7,9,4,10,5,6]
则到9时，array是：[0,1,2,3,4]
到10时，array是:[0,1,5,3,4,6]--------------------此时最长长度就是数组的最长长度
到6时，array是:[0,1,5,7,8,6]
但是，从这个数组看，它还是每次都和array中的每个元素进行比较，是怎么体现二分的呢：
就是，每次新来一个数，对于array来说，它是排好序的，
从而就将array进行二分和这个新来的数进行比较：
i=0;
j=此时array的最大的索引
while(i < j)
{
int m = (i + j) / 2;
if(array[m] < num) i = m + 1;
else j = m;
}
//最终肯定得到i==j,此时i就是那个比num小的最接近的那个数
array[i] = num;
code:
class Solution
{
public：
int lengthOfLIS(vector<int> &nums) {
vector<int> array(nums.size());
int res = 0;
for(int num : nums) {
int i = 0, j = res;
while(i < j) {
int m = (i + j) / 2;
if(array[m] < num) i = m + 1;
else j = m;
}
array[i] = num;
//如果res==j，就说明此时num比目前所有的值都大，那么最长长度res就加1
if(res == j) res++;
}
return res;
}
}
这种二分的时间复杂度就为O(nlgn)
全部评论 (0)
还没有任何评论哟~