这个数列的中,有如下4组连续的子序列:
-1, -2
-4
3, 4, 5, 6, 7, 8
11, 12
所以,很明显最长的连续子序列为:3, 4, 5, 6, 7, 8。
难点在于 要求 O(N)的时间内解决问题。所以,不可以先进行排序操作!
9 个解决方案
#1
不妨设这个数列没有重复值,否则就用hashtable剔除重复值以后再来计算。
O(n)建立一个hashtable,key是每一个a[i]-1。另外做一个数组b,b[i]意义是每个元素开始的最长递增连续子序列长度。初始化所有b[i]=1。
然后对于每一个a[i],查询a[i]它自己是不是在刚才建立的hashtable里。不在的话那就不需要做什么。在的话,那就递归下去计算b[i]的实际值。并且注意用动态规划的方法来优化(不重复计算已经计算过的b)
这样由于每个b[i]顶多被计算一次,整体复杂度依然是线性。
O(n)建立一个hashtable,key是每一个a[i]-1。另外做一个数组b,b[i]意义是每个元素开始的最长递增连续子序列长度。初始化所有b[i]=1。
然后对于每一个a[i],查询a[i]它自己是不是在刚才建立的hashtable里。不在的话那就不需要做什么。在的话,那就递归下去计算b[i]的实际值。并且注意用动态规划的方法来优化(不重复计算已经计算过的b)
这样由于每个b[i]顶多被计算一次,整体复杂度依然是线性。
#2
没太看明白
#3
……额,学习,我也看得有点晕
#4
将数据分割成2块,{} > 0 , {} < 0
那么最长连续序列有3种可能:
1 出现在{} > 0
2 出现在{} < 0
3 包含0的最长连续序列
对于大于0的数而言,可以用bitvector对数据进行O(n)时间排序,排序好后计算就简单了。
对于小于0的数而言,取反然后按1思路做
对于包含0的最长序列,其实通过前面的方法,很容易得到
那么最长连续序列有3种可能:
1 出现在{} > 0
2 出现在{} < 0
3 包含0的最长连续序列
对于大于0的数而言,可以用bitvector对数据进行O(n)时间排序,排序好后计算就简单了。
对于小于0的数而言,取反然后按1思路做
对于包含0的最长序列,其实通过前面的方法,很容易得到
#5
给4楼 happytengfei 一个反例:
数列:[1, 10000000000000000000000000000]
按照四楼的做法,
n = 2;
O(N) = 10000000000000000000000000000 >> n = 2.
数列:[1, 10000000000000000000000000000]
按照四楼的做法,
n = 2;
O(N) = 10000000000000000000000000000 >> n = 2.
#6
用位图就可以了,开2^32bit大小的内存,第一遍扫描把对应数据位置1,以后就是查找2^32bit中连续1最长有多少个,
以[5, 6, -2, -4, -1, 6, 7, 12, 8, 4, 3, 11].为例,开一个32bit的内存,从-16到+15,第一步把对应位置1,为00000000000001011001111110011000,最后就是求这个内存里面连续1的长度
以[5, 6, -2, -4, -1, 6, 7, 12, 8, 4, 3, 11].为例,开一个32bit的内存,从-16到+15,第一步把对应位置1,为00000000000001011001111110011000,最后就是求这个内存里面连续1的长度
#7
引用这个:不妨设这个数列没有重复值,否则就用hashtable剔除重复值以后再来计算
Key为给定的整数值,value给个标记值1. 遍历得到最小值Min 和最大值Max。循环遍历Min到Max(常数),每次递增1,以对应的整数在不在hash里作为条件。遍历一边可以得到连续的长度和初始值
Key为给定的整数值,value给个标记值1. 遍历得到最小值Min 和最大值Max。循环遍历Min到Max(常数),每次递增1,以对应的整数在不在hash里作为条件。遍历一边可以得到连续的长度和初始值
#8
先扫描一遍,取出最大值,按基数排序的思想,这样应该就可以取出最长子序列,踢掉重复值
#9
噶样子还叫子序列?顺序都变了
#1
不妨设这个数列没有重复值,否则就用hashtable剔除重复值以后再来计算。
O(n)建立一个hashtable,key是每一个a[i]-1。另外做一个数组b,b[i]意义是每个元素开始的最长递增连续子序列长度。初始化所有b[i]=1。
然后对于每一个a[i],查询a[i]它自己是不是在刚才建立的hashtable里。不在的话那就不需要做什么。在的话,那就递归下去计算b[i]的实际值。并且注意用动态规划的方法来优化(不重复计算已经计算过的b)
这样由于每个b[i]顶多被计算一次,整体复杂度依然是线性。
O(n)建立一个hashtable,key是每一个a[i]-1。另外做一个数组b,b[i]意义是每个元素开始的最长递增连续子序列长度。初始化所有b[i]=1。
然后对于每一个a[i],查询a[i]它自己是不是在刚才建立的hashtable里。不在的话那就不需要做什么。在的话,那就递归下去计算b[i]的实际值。并且注意用动态规划的方法来优化(不重复计算已经计算过的b)
这样由于每个b[i]顶多被计算一次,整体复杂度依然是线性。
#2
没太看明白
不妨设这个数列没有重复值,否则就用hashtable剔除重复值以后再来计算。
O(n)建立一个hashtable,key是每一个a[i]-1。另外做一个数组b,b[i]意义是每个元素开始的最长递增连续子序列长度。初始化所有b[i]=1。
然后对于每一个a[i],查询a[i]它自己是不是在刚才建立的hashtable里。不在的话那就不需要做什么。在的话,那就递归下去计算b[i]的实际值。并且注意用动态规划的方法来优化(不重复计算已经计算过的b)
这样由于每个b[i]顶多被计算一次,整体复杂度依然是线性。
#3
……额,学习,我也看得有点晕
#4
将数据分割成2块,{} > 0 , {} < 0
那么最长连续序列有3种可能:
1 出现在{} > 0
2 出现在{} < 0
3 包含0的最长连续序列
对于大于0的数而言,可以用bitvector对数据进行O(n)时间排序,排序好后计算就简单了。
对于小于0的数而言,取反然后按1思路做
对于包含0的最长序列,其实通过前面的方法,很容易得到
那么最长连续序列有3种可能:
1 出现在{} > 0
2 出现在{} < 0
3 包含0的最长连续序列
对于大于0的数而言,可以用bitvector对数据进行O(n)时间排序,排序好后计算就简单了。
对于小于0的数而言,取反然后按1思路做
对于包含0的最长序列,其实通过前面的方法,很容易得到
#5
给4楼 happytengfei 一个反例:
数列:[1, 10000000000000000000000000000]
按照四楼的做法,
n = 2;
O(N) = 10000000000000000000000000000 >> n = 2.
数列:[1, 10000000000000000000000000000]
按照四楼的做法,
n = 2;
O(N) = 10000000000000000000000000000 >> n = 2.
将数据分割成2块,{} > 0 , {} < 0
那么最长连续序列有3种可能:
1 出现在{} > 0
2 出现在{} < 0
3 包含0的最长连续序列
对于大于0的数而言,可以用bitvector对数据进行O(n)时间排序,排序好后计算就简单了。
对于小于0的数而言,取反然后按1思路做
对于包含0的最长序列,其实通过前面的方法,很容易得到
#6
用位图就可以了,开2^32bit大小的内存,第一遍扫描把对应数据位置1,以后就是查找2^32bit中连续1最长有多少个,
以[5, 6, -2, -4, -1, 6, 7, 12, 8, 4, 3, 11].为例,开一个32bit的内存,从-16到+15,第一步把对应位置1,为00000000000001011001111110011000,最后就是求这个内存里面连续1的长度
以[5, 6, -2, -4, -1, 6, 7, 12, 8, 4, 3, 11].为例,开一个32bit的内存,从-16到+15,第一步把对应位置1,为00000000000001011001111110011000,最后就是求这个内存里面连续1的长度
#7
引用这个:不妨设这个数列没有重复值,否则就用hashtable剔除重复值以后再来计算
Key为给定的整数值,value给个标记值1. 遍历得到最小值Min 和最大值Max。循环遍历Min到Max(常数),每次递增1,以对应的整数在不在hash里作为条件。遍历一边可以得到连续的长度和初始值
Key为给定的整数值,value给个标记值1. 遍历得到最小值Min 和最大值Max。循环遍历Min到Max(常数),每次递增1,以对应的整数在不在hash里作为条件。遍历一边可以得到连续的长度和初始值
没太看明白
不妨设这个数列没有重复值,否则就用hashtable剔除重复值以后再来计算。
O(n)建立一个hashtable,key是每一个a[i]-1。另外做一个数组b,b[i]意义是每个元素开始的最长递增连续子序列长度。初始化所有b[i]=1。
然后对于每一个a[i],查询a[i]它自己是不是在刚才建立的hashtable里。不在的话那就不需要做什么。在的话,那就递归下去计算b[i]的实际值。并且注意用动态规划的方法来优化(不重复计算已经计算过的b)
这样由于每个b[i]顶多被计算一次,整体复杂度依然是线性。
#8
先扫描一遍,取出最大值,按基数排序的思想,这样应该就可以取出最长子序列,踢掉重复值
#9
噶样子还叫子序列?顺序都变了