f*****e
发帖数: 2992 | 1 给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要
求这个子数组中的数组是一个连续的序列（不需要排好序）。
例如，给一个数组[4,5,1,5,7,6,8,4,1]， 最长的满足条件的子数组是[5,7,6,8,4]。因
为该子数组中，5,7,6,8,4是一个连续的序列。
求算法 | p*****2
发帖数: 21240 | 2
。因
[4,5,5,7,6,8,4,1]
输出是什么？
【在 f*****e 的大作中提到】
: 给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要
: 求这个子数组中的数组是一个连续的序列（不需要排好序）。
: 例如，给一个数组[4,5,1,5,7,6,8,4,1]， 最长的满足条件的子数组是[5,7,6,8,4]。因
: 为该子数组中，5,7,6,8,4是一个连续的序列。
: 求算法
| f*****e
发帖数: 2992 | 3 5,7,6,8,4
【在 p*****2 的大作中提到】
:
: 。因
: [4,5,5,7,6,8,4,1]
: 输出是什么？
| p*****2
发帖数: 21240 | | a*******y
发帖数: 1040 | 5 为什么N^3, 你拍好序做，排序O（nlogn）
然后有个map来存index | f*****e
发帖数: 2992 | 6 没有要求，zz的。
【在 p*****2 的大作中提到】
: BF要N^3.
: 这题复杂度什么要求？
| l*********8
发帖数: 4642 | 7 O(n^3) is for straightforward algorithm.
If you sort the array and use a map, you still need at least O(n^2), right?
【在 a*******y 的大作中提到】
: 为什么N^3, 你拍好序做，排序O（nlogn）
: 然后有个map来存index
| f*****e
发帖数: 2992 | 8 有重复元素怎么办？
【在 a*******y 的大作中提到】
: 为什么N^3, 你拍好序做，排序O（nlogn）
: 然后有个map来存index
| f*****e
发帖数: 2992 | 9 给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要
求这个子数组中的数组是一个连续的序列（不需要排好序）。
例如，给一个数组[4,5,1,5,7,6,8,4,1]， 最长的满足条件的子数组是[5,7,6,8,4]。因
为该子数组中，5,7,6,8,4是一个连续的序列。
求算法 | p*****2
发帖数: 21240 | 10
。因
[4,5,5,7,6,8,4,1]
输出是什么？
【在 f*****e 的大作中提到】
: 给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要
: 求这个子数组中的数组是一个连续的序列（不需要排好序）。
: 例如，给一个数组[4,5,1,5,7,6,8,4,1]， 最长的满足条件的子数组是[5,7,6,8,4]。因
: 为该子数组中，5,7,6,8,4是一个连续的序列。
: 求算法
| | | f*****e
发帖数: 2992 | 11 5,7,6,8,4
【在 p*****2 的大作中提到】
:
: 。因
: [4,5,5,7,6,8,4,1]
: 输出是什么？
| p*****2
发帖数: 21240 | | a*******y
发帖数: 1040 | 13 为什么N^3, 你拍好序做，排序O（nlogn）
然后有个map来存index | f*****e
发帖数: 2992 | 14 没有要求，zz的。
【在 p*****2 的大作中提到】
: BF要N^3.
: 这题复杂度什么要求？
| l*********8
发帖数: 4642 | 15 O(n^3) is for straightforward algorithm.
If you sort the array and use a map, you still need at least O(n^2), right?
【在 a*******y 的大作中提到】
: 为什么N^3, 你拍好序做，排序O（nlogn）
: 然后有个map来存index
| f*****e
发帖数: 2992 | 16 有重复元素怎么办？
【在 a*******y 的大作中提到】
: 为什么N^3, 你拍好序做，排序O（nlogn）
: 然后有个map来存index
| Y********f
发帖数: 410 | 17 O(N^2)算法：
先算出对所有i>j, i到j的区间的最大最小值，需要二维数组。这个可以O(N^2)做到
然后计算一个一维数组，其值是到该位置为止最长的无重复元素的子数组元素个数。这
个可以O(N)做到。
再利用如果一个数组没有重复元素，其最大值-最小值=元素的个数-1 算出最长的子数
组。
不知道有没有更快的算法。
。因
【在 f*****e 的大作中提到】
: 给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要
: 求这个子数组中的数组是一个连续的序列（不需要排好序）。
: 例如，给一个数组[4,5,1,5,7,6,8,4,1]， 最长的满足条件的子数组是[5,7,6,8,4]。因
: 为该子数组中，5,7,6,8,4是一个连续的序列。
: 求算法
| f*******t
发帖数: 7549 | 18 如果没有重复数字，这题是子序列构成最长连续数字的变种吧，想了一下应该能用相同
的方法，O(n)时间+O(n)空间的复杂度 | b***e
发帖数: 1419 | 19 稍微聪明一点的BF应该是n*log(n):
固定k, 长度为k的valid substring的存在性可以用O(n)判断。 对k做二分。
【在 p*****2 的大作中提到】
: BF要N^3.
: 这题复杂度什么要求？
| Y********f
发帖数: 410 | 20 "长度为k的valid substring的存在性可以用O(n)判断"
这个怎么弄？
【在 b***e 的大作中提到】
: 稍微聪明一点的BF应该是n*log(n):
: 固定k, 长度为k的valid substring的存在性可以用O(n)判断。 对k做二分。
| | | d**********x
发帖数: 4083 | 21 RMQ, O(nlogn)预处理，O(1)查询区间最大最小值
只是我对那个二分查找存疑
【在 Y********f 的大作中提到】
: "长度为k的valid substring的存在性可以用O(n)判断"
: 这个怎么弄？
| S******t
发帖数: 151 | 22 不能二分。。。
这个题目很久很久以前我在blog上写过一次……=_=
http://computationalpuzzles.wordpress.com/2011/12/05/algorithms
【在 d**********x 的大作中提到】
: RMQ, O(nlogn)预处理，O(1)查询区间最大最小值
: 只是我对那个二分查找存疑
| d**********x
发帖数: 4083 | 23 nice...
我就满足于RMQ好了。。
【在 S******t 的大作中提到】
: 不能二分。。。
: 这个题目很久很久以前我在blog上写过一次……=_=
: http://computationalpuzzles.wordpress.com/2011/12/05/algorithms
| j*****y
发帖数: 1071 | 24 rmq 是啥啊？
【在 d**********x 的大作中提到】
: nice...
: 我就满足于RMQ好了。。
| d**********x
发帖数: 4083 | | x*****0
发帖数: 452 | | G****A
发帖数: 4160 | 27 我怎么觉得你这个O(n^2)内搞不定
【在 Y********f 的大作中提到】
: O(N^2)算法：
: 先算出对所有i>j, i到j的区间的最大最小值，需要二维数组。这个可以O(N^2)做到
: 然后计算一个一维数组，其值是到该位置为止最长的无重复元素的子数组元素个数。这
: 个可以O(N)做到。
: 再利用如果一个数组没有重复元素，其最大值-最小值=元素的个数-1 算出最长的子数
: 组。
: 不知道有没有更快的算法。
:
: 。因
| c********t
发帖数: 5706 | 28 如果是允许重复的，既[4,5,6,5,7,6,8]可以是解，能不能循环切割？
1）扫一遍求出所有 min到max中的区间， 例子中 [1],[4,5,6,7,8]
2) 扫第二遍，不同区间的切割开成不同的数组[4,5] [1] [5,7,6,8,4] [1]
3）对2）的每个结果,调用1，recursion.如果1）的结果只有一个区间，既找到了一个。
最后返回最长的，当然3)中，如果区间长度小于等于已经找到的最长数组，就不用处理
了。
这个算法复杂度最坏好像是O(n^2)（都不连续），但实际应该很快吧。O(n) space, 好
处是容易写 :D
。因
【在 f*****e 的大作中提到】
: 给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要
: 求这个子数组中的数组是一个连续的序列（不需要排好序）。
: 例如，给一个数组[4,5,1,5,7,6,8,4,1]， 最长的满足条件的子数组是[5,7,6,8,4]。因
: 为该子数组中，5,7,6,8,4是一个连续的序列。
: 求算法
| b***e
发帖数: 1419 | 29 对，不能二分。k有解不能退出(k-1)有解。
【在 S******t 的大作中提到】
: 不能二分。。。
: 这个题目很久很久以前我在blog上写过一次……=_=
: http://computationalpuzzles.wordpress.com/2011/12/05/algorithms
|
|
