m*****f
发帖数: 1243 | 1 Given an array A which holds a permutation of 1,2,...,n. A sub-block A[i..j]
of an array A is called a valid block if all the numbers appearing in A[i..j]
are consecutive numbers (may not be in order）.
Given an array A= [ 7 3 4 1 2 6 5 8] the valid blocks are [3 4], [1,2], [6,5
],
[3 4 1 2], [3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8]
Give an O( n log n) algorithm to count the number of valid blocks. | m*****f
发帖数: 1243 | 2 我只有一个很不成熟的想法. 假设 array有1-n个number, 先找到所有包含最小数字的
长度为2-n的valid block, 然后把数组在1处分成两部分,递归解各部分, 有很多细节没
想清楚, 而且worst time 也是O(n^2), 求更好的方法, 以前讨论过么 | g*******y
发帖数: 1930 | | n**********8
发帖数: 188 | 4 divide conquer
先找所有经过中间的blocks，逐一左右扩展maintain min&max来判断是否是block
然后劈成两半recursive
【在 m*****f 的大作中提到】
: 我只有一个很不成熟的想法. 假设 array有1-n个number, 先找到所有包含最小数字的
: 长度为2-n的valid block, 然后把数组在1处分成两部分,递归解各部分, 有很多细节没
: 想清楚, 而且worst time 也是O(n^2), 求更好的方法, 以前讨论过么
| s*****r
发帖数: 773 | 5 怎么判断一个block是一个valid block? 比如 [5 1 2 4], 排序?
【在 n**********8 的大作中提到】
: divide conquer
: 先找所有经过中间的blocks，逐一左右扩展maintain min&max来判断是否是block
: 然后劈成两半recursive
| k*k
发帖数: 49 | 6 some thoughts...
build tree bottom up. nlogn tree construction.
(7) (3) (4) (1) (2) (6) (5) (8)
1) traverse:
merge adj element to produce
(7) (3,4) (1,2) (6,5) (8)
2) traverse again:
(7) (3,4,1,2) (6,5) (8)
3) traverse again
(7) (3,4,1,2,6,5) (8)
4) again
(7, 3, 4, 1, 2, 6, 5) (8)
5) again
(7, 3, 4, 1, 2, 6, 5, 8)
two adj. blocks merge if max(max(Block1), max(Block2)) - min(min(Block1), min(Block2)) == sizeof(block1 + block2) | h**k
发帖数: 3368 | 7 how about the case
(3) (5) (1, 2) (6) (4)
Could your algorithm to get the valid block (3,5,1,2,6,4)?
min(Block2)) == sizeof(block1 + block2)
【在 k*k 的大作中提到】
: some thoughts...
: build tree bottom up. nlogn tree construction.
: (7) (3) (4) (1) (2) (6) (5) (8)
: 1) traverse:
: merge adj element to produce
: (7) (3,4) (1,2) (6,5) (8)
: 2) traverse again:
: (7) (3,4,1,2) (6,5) (8)
: 3) traverse again
: (7) (3,4,1,2,6,5) (8)
| k*k
发帖数: 49 | 8 (3) (5) (1, 2) (6) (4)
(3) (5) failed
(5) (1,2) failed
(1,2) (6) failed
(6) (4) failed
(3) (5) (1, 2) failed
(5) (1,2) (6) failed
(1,2) (6) (4) failed
(3) (5) (1, 2) (6) (4)
k adj blocks can merge if
max(max(block 1...k)) - min(min(block 1...k)) == sizeof(block 1...k)
the case u give... may be one of the worst case scenario...
it is similar to the case that all nodes in the tree lines up as a straight
line, so the insertion will take n instead of log n then the complexity
becomes n^2 | h**k
发帖数: 3368 | 9 en, so your algorithm is also O(n*n).
【在 k*k 的大作中提到】
: (3) (5) (1, 2) (6) (4)
: (3) (5) failed
: (5) (1,2) failed
: (1,2) (6) failed
: (6) (4) failed
: (3) (5) (1, 2) failed
: (5) (1,2) (6) failed
: (1,2) (6) (4) failed
: (3) (5) (1, 2) (6) (4)
: k adj blocks can merge if
| k*k
发帖数: 49 | 10 i think....
my "sol":
average case n log n, worst case n^2
just like constructing a binary search tree from a sequence of number
n log n average, n^2 worst... but we generally consider construction of a
binary search tree has complexity of nlogn | h**k
发帖数: 3368 | 11
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
你可以再去查查看
【在 k*k 的大作中提到】
: i think....
: my "sol":
: average case n log n, worst case n^2
: just like constructing a binary search tree from a sequence of number
: n log n average, n^2 worst... but we generally consider construction of a
: binary search tree has complexity of nlogn
| k*k
发帖数: 49 | 12 http://en.wikipedia.org/wiki/Binary_search_tree
under insertion:
In either version, this operation requires time proportional to the height
of the tree in the worst case, which is O(log n) time in the average case
over all trees, but Ω(n) time in the worst case.
u have n element to insert... so worst case n^2 | V**0
发帖数: 889 | 13 我也觉得这题得用tree
【在 k*k 的大作中提到】
: http://en.wikipedia.org/wiki/Binary_search_tree
: under insertion:
: In either version, this operation requires time proportional to the height
: of the tree in the worst case, which is O(log n) time in the average case
: over all trees, but Ω(n) time in the worst case.
: u have n element to insert... so worst case n^2
| h**k
发帖数: 3368 | 14
当然是建balanced binary tree了，那样worst case 就是O(nlogn)
【在 k*k 的大作中提到】
: http://en.wikipedia.org/wiki/Binary_search_tree
: under insertion:
: In either version, this operation requires time proportional to the height
: of the tree in the worst case, which is O(log n) time in the average case
: over all trees, but Ω(n) time in the worst case.
: u have n element to insert... so worst case n^2
|
|
