g*****u
发帖数: 298 | 1 1. Given a M*N matrix A in which all the elements in a row and all the
elements in a column are strictly increasing. Find a path from the smallest
element (ie A[0][0]) to the largest element (ie A[M-1][N-1]) such that the
sum of the elements in the path is maximum. Time Complexity O(m+n). Use
efficient space.
我觉得这个隐含只能向右和向下走。
2. Given a M*N matrix A in which all the elements in a row and all the
elements in a column are strictly increasing. Print the numbers in ascending
order. |
b***e
发帖数: 1419 | 2 The first one is classic dynamic programming: compute the optimal path from
any position to bottom right using the induction:
p(i, j) = v(i, j) + max(p(i + 1, j), p(i, j + 1))
and always do the positions to the right of the equation first. |
g*****u
发帖数: 298 | 3 你这个是O(m+n)的么？
from
【在 b***e 的大作中提到】
: The first one is classic dynamic programming: compute the optimal path from
: any position to bottom right using the induction:
: p(i, j) = v(i, j) + max(p(i + 1, j), p(i, j + 1))
: and always do the positions to the right of the equation first.
|
C****N
发帖数: 108 | 4 u mean
p(i,j) = v(i, j) + max(p(i-1,j), p(i,j-1) )
ba
from
【在 b***e 的大作中提到】
: The first one is classic dynamic programming: compute the optimal path from
: any position to bottom right using the induction:
: p(i, j) = v(i, j) + max(p(i + 1, j), p(i, j + 1))
: and always do the positions to the right of the equation first.
|
C****N
发帖数: 108 | 5 this is o(mn)
and it doesn't take advantage of the strictly increasing property
so u mean we only can go down or right, correct?
【在 g*****u 的大作中提到】
: 你这个是O(m+n)的么？
:
: from
|
kb
发帖数: 73 | 6 For the first one, simple greedy may work, which is O(m+n).
Go down or right, whichever is larger. Go straight down if reach right most column. |
kb
发帖数: 73 | 7 For the second one, use merge sort. Either merge columns or rows. O(mn\log
min{m,n}). |
C****N
发帖数: 108 | 8 1 2 3
4 5 98
96 97 100
most column.
【在 kb 的大作中提到】
: For the first one, simple greedy may work, which is O(m+n).
: Go down or right, whichever is larger. Go straight down if reach right most column.
|
kb
发帖数: 73 | 9 And if you reach the bottom, go straight right. (Here I assume the path is
in increasing order.)
For the problem above, the answer is 1,4,96,97,100 |
S**Y
发帖数: 136 | 10 1 2 98
4 5 99
96 97 100
please be responsible
【在 kb 的大作中提到】
: And if you reach the bottom, go straight right. (Here I assume the path is
: in increasing order.)
: For the problem above, the answer is 1,4,96,97,100
|
|
|
b***e
发帖数: 1419 | 11 Dude, there is no O(m+n), and the best you get is O(m*n).
You have to access each cell in the matrix at least once. Otherwise, assume
you miss one element, and this element happens to be infinity(a.k.a. very
big), you are cooked.
【在 g*****u 的大作中提到】
: 你这个是O(m+n)的么？
:
: from
|
X****r
发帖数: 3557 | 12 Not really. Given the special constraint of this matrix, in O(n+m) time
you can compute the upper limit of the maximum sum by adding up the right-
most column and the bottom row.
assume
very
【在 b***e 的大作中提到】
: Dude, there is no O(m+n), and the best you get is O(m*n).
: You have to access each cell in the matrix at least once. Otherwise, assume
: you miss one element, and this element happens to be infinity(a.k.a. very
: big), you are cooked.
|
S**Y
发帖数: 136 | 13 agree
觉得这道题不太可能有o(m+n)算法
u have to access each element
assume
【在 b***e 的大作中提到】
: Dude, there is no O(m+n), and the best you get is O(m*n).
: You have to access each cell in the matrix at least once. Otherwise, assume
: you miss one element, and this element happens to be infinity(a.k.a. very
: big), you are cooked.
|
S**Y
发帖数: 136 | 14 so what?
看清楚题目
【在 X****r 的大作中提到】
: Not really. Given the special constraint of this matrix, in O(n+m) time
: you can compute the upper limit of the maximum sum by adding up the right-
: most column and the bottom row.
:
: assume
: very
|
X****r
发帖数: 3557 | 15 我只是说blaze 刚才的文章不能证明O(m+n)的算法不存在，并非提出一个具体的算法。
【在 S**Y 的大作中提到】
: so what?
: 看清楚题目
|
S**Y
发帖数: 136 | 16 我觉得have to check each element
因为你永远不知道each element的后面有什么
无法排除掉哪个element不用走
【在 X****r 的大作中提到】
: 我只是说blaze 刚才的文章不能证明O(m+n)的算法不存在，并非提出一个具体的算法。
|
n******t
发帖数: 4406 | 17 我认为optimal 应该介于m*n 和m+n之间
【在 S**Y 的大作中提到】
: 我觉得have to check each element
: 因为你永远不知道each element的后面有什么
: 无法排除掉哪个element不用走
|
S**Y
发帖数: 136 | 18 网神姐姐能够详述一下?
【在 n******t 的大作中提到】
: 我认为optimal 应该介于m*n 和m+n之间
|
p***o
发帖数: 1252 | 19 如果不能斜着走，他估计的不对，你估计的是对的，某些情况每个元素都要访问到，
复杂度是\Theta(mn)。比如:
A(i,j)=(i+j)*2^{mn}+B(i,j), 这里B(i,j)是2^0,2^1,...,2^{mn-1}的一个排列。
这样找最长路径比找B的最大元素难，至少需要\Omega(mn)的时间。
【在 S**Y 的大作中提到】
: 网神姐姐能够详述一下?
|
b***e
发帖数: 1419 | 20 Consider A where Aij = i + j, e.g,
0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6
Apparently, all paths are the same. So your algorithm will find one of
them. Assume your algorithm doens't access an element e, then I construct
A' from A by having e = e + 0.5. Apparently, your algorithm will work
exactly the same on A' as on A, because you don't even care about e. Now
you are cooked.
【在 X****r 的大作中提到】
: Not really. Given the special constraint of this matrix, in O(n+m) time
: you can compute the upper limit of the maximum sum by adding up the right-
: most column and the bottom row.
:
: assume
: very
|
|
|
t****t
发帖数: 6806 | 21 now this is a correct proof.
【在 b***e 的大作中提到】
: Consider A where Aij = i + j, e.g,
: 0 1 2 3
: 1 2 3 4
: 2 3 4 5
: 3 4 5 6
: Apparently, all paths are the same. So your algorithm will find one of
: them. Assume your algorithm doens't access an element e, then I construct
: A' from A by having e = e + 0.5. Apparently, your algorithm will work
: exactly the same on A' as on A, because you don't even care about e. Now
: you are cooked.
|
m*****k
发帖数: 731 | 22 what???
1 2 99
3 4 100
most column.
【在 kb 的大作中提到】
: For the first one, simple greedy may work, which is O(m+n).
: Go down or right, whichever is larger. Go straight down if reach right most column.
|
S**Y
发帖数: 136 | 23 a nice one.
【在 b***e 的大作中提到】
: Consider A where Aij = i + j, e.g,
: 0 1 2 3
: 1 2 3 4
: 2 3 4 5
: 3 4 5 6
: Apparently, all paths are the same. So your algorithm will find one of
: them. Assume your algorithm doens't access an element e, then I construct
: A' from A by having e = e + 0.5. Apparently, your algorithm will work
: exactly the same on A' as on A, because you don't even care about e. Now
: you are cooked.
|
s********r
发帖数: 9 | 24 go to check francis Yao's paper. It may help you. |
kb
发帖数: 73 | 25
Don't be so mean.
PS: Where is your answer to any of these two questions?
【在 S**Y 的大作中提到】
: 1 2 98
: 4 5 99
: 96 97 100
: please be responsible
|
kb
发帖数: 73 | 26 Any O(mn) algorithm for the second question? |
J*******n
发帖数: 511 | |
y*******n
发帖数: 195 | 28 In Q1, can we do diagonal movement or just horizontal and vertical ones?
My first instinct tells me the question has something to do with Dijkstra's
algorithm, but then the time complexity cannot be O(m+n).
smallest
ascending
【在 g*****u 的大作中提到】
: 1. Given a M*N matrix A in which all the elements in a row and all the
: elements in a column are strictly increasing. Find a path from the smallest
: element (ie A[0][0]) to the largest element (ie A[M-1][N-1]) such that the
: sum of the elements in the path is maximum. Time Complexity O(m+n). Use
: efficient space.
: 我觉得这个隐含只能向右和向下走。
: 2. Given a M*N matrix A in which all the elements in a row and all the
: elements in a column are strictly increasing. Print the numbers in ascending
: order.
|
