狗家题讨论 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

狗家题讨论

狗家题讨论# JobHunting - 待字闺中

c*n2015-05-02 07:05

1 楼

1. Given a array of integers , find 3 indexes i,j,k such that, i] < a[j] < a[k]. Best possible is a O(n) algorithm.
这个就现在这样可以就设三个点，每个新点来了对比这三个参照。就是写好些if else
但如果推广到要求找K element 长的递增的subsequence，怎么办？I guess u could
simply use "find the longest increasing subsequence", but if the actual LIS
is much longer than K, maybe simpler methods exist to simply find ONE
subsequence longer than K?

B*l2015-05-02 07:05

2 楼

用一个stack，然后go through a，碰到a[i]把stack里大于等于a[i]的都pop出去，然
后push a[i]到stack，stack里的数是递增的，check stack size就行。复杂度O(n)。

[i
else
could
LIS

【在 c******n 的大作中提到】

: 1. Given a array of integers , find 3 indexes i,j,k such that, i: ] < a[j] < a[k]. Best possible is a O(n) algorithm.
: 这个就现在这样可以就设三个点，每个新点来了对比这三个参照。就是写好些if else
: 但如果推广到要求找K element 长的递增的subsequence，怎么办？I guess u could
: simply use "find the longest increasing subsequence", but if the actual LIS
: is much longer than K, maybe simpler methods exist to simply find ONE
: subsequence longer than K?

i*s2015-05-02 07:05

3 楼

一个例子: [2, 3, 1, 4], 然后 k = 3

【在 B******l 的大作中提到】

: 用一个stack，然后go through a，碰到a[i]把stack里大于等于a[i]的都pop出去，然
: 后push a[i]到stack，stack里的数是递增的，check stack size就行。复杂度O(n)。
:
: [i
: else
: could
: LIS

l*s2015-05-02 07:05

4 楼

stack size>1时不能pop

【在 B******l 的大作中提到】

A*t2015-05-02 07:05

5 楼

这样可以么用两个数组分别表示最大和最小的index 保持这两个数组是递减的
例如50， 60， 40， 30， 20， 35， 36；
min(的值) 50; 50; 50,40; 50,40,30; 50,40,30,20; 50,40,30,20
max(的值) ;60; 60; 60; 60; 60, , ,
35
int n = arr.length;
int[] min = new int[n];
int[] max = new int[n];
min[0] = 0;
int i = 0;
int j = -1;
for(int k=1; kif(arr[k]min[++i] = k;
}
else if(j>=0 && arr[min[i]]
arr[min[i]){ //介于二者中间
max[i] = arr[k];
j=i;
}
else if(j>=0 && arr[k]>arr[max[j]]){ //大于最大的则找到
return i + "," + j + "," + k;
}
}
return "not found'

A*e2015-05-02 07:05

6 楼

LIS，到k个就停止不行吗？

[i
else
could
LIS

【在 c******n 的大作中提到】

c*n2015-05-02 07:05

7 楼

还没仔细看。但k==2的时候，你需要记录最低点（一个点）， k==3的时候，需要记
录前面两个点，如果又出现比前面阶梯的最低点还低的点，还要记录新的最低点。
照这样照猫画虎，那一般情况需要记录k-1个台阶，k-2个台阶，k-3个。。。。。1个
，这k^个点把vertical space 分成k^2个区间都要比较

【在 A******t 的大作中提到】

: 这样可以么用两个数组分别表示最大和最小的index 保持这两个数组是递减的
: 例如50， 60， 40， 30， 20， 35， 36；
: min(的值) 50; 50; 50,40; 50,40,30; 50,40,30,20; 50,40,30,20
: max(的值) ;60; 60; 60; 60; 60, , ,
: 35
: int n = arr.length;
: int[] min = new int[n];
: int[] max = new int[n];
: min[0] = 0;
: int i = 0;

S*a2015-05-02 07:05

8 楼

两个基本思路：
1、先从简单入手，找2个数而不是3个数，看规律是啥。
2. 记得leetcode有道类似的题，是index进栈，而不是值进栈。
晚上再想想。

[i
else
could
LIS

【在 c******n 的大作中提到】

h*32015-05-02 07:05

9 楼

貌似你这两个else if 永远也执行不了啊

【在 A******t 的大作中提到】

w*w2015-05-02 07:05

10 楼

可以从左至右 scan 存当前见到的 “最小”递增序列（对所有长从1到K）的值这里
序列的大小是看最大的值存在数组y里然后每到一个新值 x 作 update 就是看如果x
介于y[k] 与y[k+1]之间就设y[k+1]=x 因为y一定是单调减可以做到 n log(K) 时间
K空间

c*n2015-05-02 07:05

11 楼

见我上面帖子，一个递增序列不够，你怎么定义“最小”？序列第一个点最小？
how about
2 3 1 1.5 2
or
2 3. 1. 4

x

【在 w***w 的大作中提到】

: 可以从左至右 scan 存当前见到的 “最小”递增序列（对所有长从1到K）的值这里
: 序列的大小是看最大的值存在数组y里然后每到一个新值 x 作 update 就是看如果x
: 介于y[k] 与y[k+1]之间就设y[k+1]=x 因为y一定是单调减可以做到 n log(K) 时间
: K空间

i*h2015-05-02 07:05

12 楼

如果有解，i，j，k
推论1。a[i] 是０－i里最小的，否则可以被前面更小的数置换，同樣有解
推论2。a[k] 是 k－Ｎ里最大的，否则可以被后面更大的数置换，同樣有解
算法：
同时从两头开始，前面存当前最小数a［i］，后面存当前最大数a［k］，如果a［i］>a
[k], 向中间移动
如果a［i］

w*w2015-05-02 07:05

13 楼

最大值最后一个点
你的例子 y=（y[1],y[2],y[3]) 从左至右是 (2, null,null) (2,3,null) (1,3,null)
(1,1.5,null) (1,1.5,2) 所以存在递增3序列

i*h2015-05-02 07:05

14 楼

最后那解法好象不行，修改一下
上面推论1和2继续成立
推论3，中间数a[j]同时不满足推论1和2
解法：
从头开始，标注所有当前最小数－Ｎ
从尾巴倒退标注所有当前最大数－Ｎ
再次遍历数组找到既沒有最小也沒有最大标记的数，如果找到，必然能以此为中间值找
到符合条件的i，j，k
否则无解
Ｏ（Ｎ）

>a

【在 i***h 的大作中提到】

: 如果有解，i，j，k
: 推论1。a[i] 是０－i里最小的，否则可以被前面更小的数置换，同樣有解
: 推论2。a[k] 是 k－Ｎ里最大的，否则可以被后面更大的数置换，同樣有解
: 算法：
: 同时从两头开始，前面存当前最小数a［i］，后面存当前最大数a［k］，如果a［i］>a
: [k], 向中间移动
: 如果a［i］

c*n2015-05-02 07:05

15 楼

你这个例子里面有一步错了，可以show 给你好像你对条件要求理解有误
2 3 1 1.5 2
2,null,null
2,3,null
1,3,null *********这一步有错，3 在 1前面，不能算increasing sequence

null)

【在 w***w 的大作中提到】

: 最大值最后一个点
: 你的例子 y=（y[1],y[2],y[3]) 从左至右是 (2, null,null) (2,3,null) (1,3,null)
: (1,1.5,null) (1,1.5,2) 所以存在递增3序列

c*n2015-05-02 07:05

16 楼

如果你确实错了的话， point 就是现在检查到的 increasing sequence , 不仅要最低
（就像你说的以sequence top大小比较），另一个dimension 是已经积累的seqence 长
度，两个都要比较的话就成就了 LIS 的 n^2

【在 c******n 的大作中提到】

: 你这个例子里面有一步错了，可以show 给你好像你对条件要求理解有误
: 2 3 1 1.5 2
: 2,null,null
: 2,3,null
: 1,3,null *********这一步有错，3 在 1前面，不能算increasing sequence
:
: null)

w*w2015-05-02 07:05

17 楼

y[k]记的是到目前为至“最小”的长度为k的递增序列的最大值所以 (1,3,null) 1 对
应长度为1的递增序列（就是最小值）而3的对应序列是 2,3.

w*w2015-05-02 07:05

18 楼

发个福利，上 code 吧 (这里k对应长为k+1的序列，POS_INFTY是上文中的null）这里
是从小到大比，是 O(nK) 时间。y 单调增，如果二分查找是 O(n log(K)).
bool has_K_increasing_sequence(vector X, int K) {
vector y(K, POS_INFTY);
for(double x: X) {
for(int k=0; kif(x}
}
return y[K-1] != POS_INFTY;
}

c*n2015-05-02 07:05

19 楼

很清晰，谢谢。
我开始总在想要记全部 k 个sequence , 那就有k^2 个区间要比较，就想混了。实际
只是max 管用。

【在 w***w 的大作中提到】

: 发个福利，上 code 吧 (这里k对应长为k+1的序列，POS_INFTY是上文中的null）这里
: 是从小到大比，是 O(nK) 时间。y 单调增，如果二分查找是 O(n log(K)).
: bool has_K_increasing_sequence(vector X, int K) {
: vector y(K, POS_INFTY);
: for(double x: X) {
: for(int k=0; k: if(x: }
: }
: return y[K-1] != POS_INFTY;

c*n2015-05-02 07:05

20 楼

对比LIS 有一点有趣的相似： LIS 是在每一个前方的点都看partial increasing
sequence , 这里只管k 长的partial . LIS 还得记录partial 长度，这里就直接
encode 到index 里面了

【在 c******n 的大作中提到】

: 很清晰，谢谢。
: 我开始总在想要记全部 k 个sequence , 那就有k^2 个区间要比较，就想混了。实际
: 只是max 管用。

c*n2015-05-02 07:05

21 楼

用这个办法set K=N 就是这个（最后一段）
http://www.algorithmist.com/index.php/Longest_Increasing_Subseq

【在 c******n 的大作中提到】

: 对比LIS 有一点有趣的相似： LIS 是在每一个前方的点都看partial increasing
: sequence , 这里只管k 长的partial . LIS 还得记录partial 长度，这里就直接
: encode 到index 里面了

l*z2015-05-02 07:05

22 楼

一遍扫描的解法：
int[] check(int [] A){
int N = A.length;
if(N<3) return null;
int min = 0;
int[] ret = new int[3];
ret[0] = 0;
ret[1] = -1;

for(int i=1; iif(ret[1] < 0){
if(A[i]min = i;
ret[0] = i;
}else if(A[i]>A[min]){
ret[1] = i;
}
}
else{
//has i, j
if(A[i]>A[ret[1]]){
//found i , j, k
ret[2] = i;
return ret;
}else if(A[i]> A[ret[0]]){
ret[1] = i;
}else if(A[i] > A[min]){
ret[0] = min;
ret[1] = i;
}else if(A[i]min = i;
}
}
}
return null;
}

i*s2015-05-02 07:05

23 楼

赞思路。或者用O(n)空间，O(n)时间的，代码简单一点。LIS解法也行。这个需要分析
清楚为什么要保存min，赞

【在 l*****z 的大作中提到】

: 一遍扫描的解法：
: int[] check(int [] A){
: int N = A.length;
: if(N<3) return null;
: int min = 0;
: int[] ret = new int[3];
: ret[0] = 0;
: ret[1] = -1;
:
: for(int i=1; i

s*x2015-05-02 07:05

24 楼

赞一个！

【在 l*****z 的大作中提到】

: 一遍扫描的解法：
: int[] check(int [] A){
: int N = A.length;
: if(N<3) return null;
: int min = 0;
: int[] ret = new int[3];
: ret[0] = 0;
: ret[1] = -1;
:
: for(int i=1; i