请教一下关于建家庭摄影棚# PhotoGear - 摄影器材
l*d
1 楼
一个任意的数组,找出一个严格单调递增的最长子序列。
例如: { 3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8 } –> output: {0, 1, 2, 4, 5, 6, 8}
网上看到人说有个很简洁巧妙的算法,能在O(N log N)时间和O(N)空间做出来!方法就
是始终保持一个单增的序列,然后新来的数如果比当前最大还大就append在后面,否则
在单增序列里面做binary search,替换相应位置的数。
比如给定src[ ]:
3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8
定义一个新数组,value a[i]是当前数src[i]在包含自己的最长序列里的index。如果
src[i] > src[i-1], 那么a[i] = a[i-1] + 1, 否则,binary search 找到src[i] <
src[k-1],
src: 3, 0, 1, 7, 2, 4, 9, 10, 5, 15, 8
a: 1 1 2 3 3 4 5 6 5 7 6
可是我觉得这个方法不对啊,举个简单例子:给
src: {7, 8, 1, 10}
a: 1 2 1 ?
按照他的算法,到10的时候src[i] > src[i-1], 那么a[i] = a[i-1] + 1
可是10应该是从前面8开始算。那个binary search 怎么回事,我也没看明白。
例如: { 3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8 } –> output: {0, 1, 2, 4, 5, 6, 8}
网上看到人说有个很简洁巧妙的算法,能在O(N log N)时间和O(N)空间做出来!方法就
是始终保持一个单增的序列,然后新来的数如果比当前最大还大就append在后面,否则
在单增序列里面做binary search,替换相应位置的数。
比如给定src[ ]:
3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8
定义一个新数组,value a[i]是当前数src[i]在包含自己的最长序列里的index。如果
src[i] > src[i-1], 那么a[i] = a[i-1] + 1, 否则,binary search 找到src[i] <
src[k-1],
src: 3, 0, 1, 7, 2, 4, 9, 10, 5, 15, 8
a: 1 1 2 3 3 4 5 6 5 7 6
可是我觉得这个方法不对啊,举个简单例子:给
src: {7, 8, 1, 10}
a: 1 2 1 ?
按照他的算法,到10的时候src[i] > src[i-1], 那么a[i] = a[i-1] + 1
可是10应该是从前面8开始算。那个binary search 怎么回事,我也没看明白。