K*****Y
发帖数: 629 | 1 Given an NxN matrix, which satisfies the property that, for any element a_ij,
it satisfies a_ij > a_i,j-1, a_ij > a_i+1,j, a_ij > a_i+1,j+1 (i.e, it is
greater than its neighbor immediately to its left, top, and top-left).
The question is to find an algorithm with O(N) complexity to query whether an
arbitrary number x is in the matrix or not. i.e, whether there exist i, j,
such that a_ij==x.
Thank you very much for the help! | m****h
发帖数: 261 | 2 compare x with a_11, a_22, ..., until a_{i-1,i-1} < x < a_{i,i}. Then search
all a_i,j and a_j,i for j
a_ij,
an
【在 K*****Y 的大作中提到】
: Given an NxN matrix, which satisfies the property that, for any element a_ij,
: it satisfies a_ij > a_i,j-1, a_ij > a_i+1,j, a_ij > a_i+1,j+1 (i.e, it is
: greater than its neighbor immediately to its left, top, and top-left).
: The question is to find an algorithm with O(N) complexity to query whether an
: arbitrary number x is in the matrix or not. i.e, whether there exist i, j,
: such that a_ij==x.
: Thank you very much for the help!
| y***u
发帖数: 101 | 3 Let's solve a slightly more general problem where the matrix is m*n
(1) Binary search on the diagonal a_{11} ... a_{min(m,n),min(m,n)},
and find i s.t. a_{ii} < x < a{i+1, i+1}
(2) Solve the problem recursively on two submatrices: A(1:i,i+1:n) and
A(i+1:m,1:i)
Assume the cost is f(m, n), we have
f(m, n) <= log(min(m,n)) + max_i { f(i,n-i) + f(m-i,i) }
Solving the recursion gives you f(m, n) = O(m+n).
【在 K*****Y 的大作中提到】
: Given an NxN matrix, which satisfies the property that, for any element a_ij,
: it satisfies a_ij > a_i,j-1, a_ij > a_i+1,j, a_ij > a_i+1,j+1 (i.e, it is
: greater than its neighbor immediately to its left, top, and top-left).
: The question is to find an algorithm with O(N) complexity to query whether an
: arbitrary number x is in the matrix or not. i.e, whether there exist i, j,
: such that a_ij==x.
: Thank you very much for the help!
| s*m
发帖数: 34 | 4
f(1,n)=? n? then f(n,n)=?
【在 y***u 的大作中提到】
: Let's solve a slightly more general problem where the matrix is m*n
: (1) Binary search on the diagonal a_{11} ... a_{min(m,n),min(m,n)},
: and find i s.t. a_{ii} < x < a{i+1, i+1}
: (2) Solve the problem recursively on two submatrices: A(1:i,i+1:n) and
: A(i+1:m,1:i)
: Assume the cost is f(m, n), we have
: f(m, n) <= log(min(m,n)) + max_i { f(i,n-i) + f(m-i,i) }
: Solving the recursion gives you f(m, n) = O(m+n).
| y***u
发帖数: 101 | 5
em, solving this recursion directly may not be easy. but we can use
induction to show that f(m,n) <= a (m+n) - b log(m+n), where a and b
are constants to be determined. the base case is then f(1,n) = n.
【在 s*m 的大作中提到】
:
: f(1,n)=? n? then f(n,n)=?
| l*****g
发帖数: 49 | 6 Here is a simpler solution (no recursion, etc.), it can be thought of as a
"walk" on the matrix.
First of all, fix the orientation of the matrix so that each row/column is
monotonically increasing from left/up to right/down.
Start at a[n,1] and walk up in the first column (that is, search x in column
1). Either we find x, or we stop at two elements a[i,1] and a[i+1,1] such that
a[i,1] < x < a[i+1,1]. This means x is not in column 1, then we "walk" right
to a[i,2]. Now comes the important observa
【在 y***u 的大作中提到】
:
: em, solving this recursion directly may not be easy. but we can use
: induction to show that f(m,n) <= a (m+n) - b log(m+n), where a and b
: are constants to be determined. the base case is then f(1,n) = n.
| u*****n
发帖数: 160 | 7 你这个算法worst case 要O(n^2). worst case 就是 那个你要找的值不存在或者在一个
角落里边.
that
【在 l*****g 的大作中提到】
: Here is a simpler solution (no recursion, etc.), it can be thought of as a
: "walk" on the matrix.
: First of all, fix the orientation of the matrix so that each row/column is
: monotonically increasing from left/up to right/down.
: Start at a[n,1] and walk up in the first column (that is, search x in column
: 1). Either we find x, or we stop at two elements a[i,1] and a[i+1,1] such that
: a[i,1] < x < a[i+1,1]. This means x is not in column 1, then we "walk" right
: to a[i,2]. Now comes the important observa
| l*****g
发帖数: 49 | 8
No, I don't think so.
My algorithm will take WORST CASE O(n) time (even x does not exsit in
matrix). Please look at it carefully.
Could you show me an example that it takes O(n^2) time?
个
column
right
we
to
and
【在 u*****n 的大作中提到】
: 你这个算法worst case 要O(n^2). worst case 就是 那个你要找的值不存在或者在一个
: 角落里边.
:
: that
| l*****g
发帖数: 49 | 9
In fact, here is a sample plot of the walk taken by the algorithm, even
assuming that x does not exist in the matrix.
Column
1 2 ... n
Row |
1 _______|
2 |
______|
|
. _|
. |
. |
_|
|
|
n |
Remember that each row is monotonically increasing from left to right and each
column is monotonically increasing from top to bottom.
个
column
right
we
to
and
【在 u*****n 的大作中提到】
: 你这个算法worst case 要O(n^2). worst case 就是 那个你要找的值不存在或者在一个
: 角落里边.
:
: that
| c****r
发帖数: 185 | 10 It could be improved.
Binary search the first column, find i, i+1.
Then binary search row i.
It takes O(logm+logn)
BTW, by hashing all entries, it takes O(1).
一
a
is
such
elements
m*n
a_{min(m,n),min(m,n)},
【在 l*****g 的大作中提到】
:
: In fact, here is a sample plot of the walk taken by the algorithm, even
: assuming that x does not exist in the matrix.
: Column
: 1 2 ... n
: Row |
: 1 _______|
: 2 |
: ______|
: |
| | | u*****n
发帖数: 160 | 11 Sorry that I misunderstood your solution.
each
一
a
is
such
elements
【在 l*****g 的大作中提到】
:
: In fact, here is a sample plot of the walk taken by the algorithm, even
: assuming that x does not exist in the matrix.
: Column
: 1 2 ... n
: Row |
: 1 _______|
: 2 |
: ______|
: |
| l*****g
发帖数: 49 | 12
No, no. It is true that you can binary search the first column, but
you can NOT binary search among rows. I don't want to explain the reason
here (it takes me sometime to write down), but you can figure it out.
In fact, I can prove a lower bound of \Omega(n) on the running time
of any such (deterministic) algorithm. So your O( logm + logn ) running
time is not correct.
【在 c****r 的大作中提到】
: It could be improved.
: Binary search the first column, find i, i+1.
: Then binary search row i.
: It takes O(logm+logn)
: BTW, by hashing all entries, it takes O(1).
:
: 一
: a
: is
: such
| u*****n
发帖数: 160 | 13 Are you using decision tree to prove the low bound? It's very interesting to
know how to prove the low bound.
【在 l*****g 的大作中提到】
:
: No, no. It is true that you can binary search the first column, but
: you can NOT binary search among rows. I don't want to explain the reason
: here (it takes me sometime to write down), but you can figure it out.
: In fact, I can prove a lower bound of \Omega(n) on the running time
: of any such (deterministic) algorithm. So your O( logm + logn ) running
: time is not correct.
| y***u
发帖数: 101 | 14 This is a nice one, and has a better constant.
【在 l*****g 的大作中提到】
: Here is a simpler solution (no recursion, etc.), it can be thought of as a
: "walk" on the matrix.
: First of all, fix the orientation of the matrix so that each row/column is
: monotonically increasing from left/up to right/down.
: Start at a[n,1] and walk up in the first column (that is, search x in column
: 1). Either we find x, or we stop at two elements a[i,1] and a[i+1,1] such that
: a[i,1] < x < a[i+1,1]. This means x is not in column 1, then we "walk" right
: to a[i,2]. Now comes the important observa
| y***u
发帖数: 101 | 15 副对角线上的元素彼此之间没联系，所以必须都看一下。
【在 u*****n 的大作中提到】
: Are you using decision tree to prove the low bound? It's very interesting to
: know how to prove the low bound.
| s*m
发帖数: 34 | 16 这个是标准的解法，不需要ai,j>a_i+1,j+1的条件。complexity: m+n-1.
【在 y***u 的大作中提到】
: This is a nice one, and has a better constant.
| j*****h
发帖数: 62 | 17 ai,j>a_i+1,j+1 不就是前两个条件的推论嘛。
【在 s*m 的大作中提到】
: 这个是标准的解法，不需要ai,j>a_i+1,j+1的条件。complexity: m+n-1.
| s*m
发帖数: 34 | 18 是吗？
【在 j*****h 的大作中提到】
: ai,j>a_i+1,j+1 不就是前两个条件的推论嘛。
| j*****h
发帖数: 62 | 19 按列和按行都排好序了，自然某方向的对角线也排好序了。
【在 s*m 的大作中提到】
: 是吗？
| r****c
发帖数: 2585 | 20 nice
one
column
that
right
we
to
【在 y***u 的大作中提到】
: This is a nice one, and has a better constant.
| | | r****c
发帖数: 2585 | 21 right
one condition is redundant
【在 j*****h 的大作中提到】
: 按列和按行都排好序了，自然某方向的对角线也排好序了。
| l*****g
发帖数: 49 | 22
yes, the decision tree model (or even the simpler comparison tree
model). See yixiu post 3562.
【在 u*****n 的大作中提到】
: Are you using decision tree to prove the low bound? It's very interesting to
: know how to prove the low bound.
| r****c
发帖数: 2585 | 23 Of coz the average time may be better. (also amortized?
to
【在 l*****g 的大作中提到】
:
: yes, the decision tree model (or even the simpler comparison tree
: model). See yixiu post 3562.
| s*m
发帖数: 34 | 24 可是现在的题目好像是说副对角线也排好序了
【在 y***u 的大作中提到】
: 副对角线上的元素彼此之间没联系，所以必须都看一下。
| s*m
发帖数: 34 | 25 a_ij > a_i,j-1, a_ij > a_i+1,j, a_ij > a_i+1,j+1
1,2怎么推出3来的？
【在 r****c 的大作中提到】
: right
: one condition is redundant
| j*****h
发帖数: 62 | 26 他写错了。呵呵。他的文字描述和数学描述稍有不同。
【在 s*m 的大作中提到】
: a_ij > a_i,j-1, a_ij > a_i+1,j, a_ij > a_i+1,j+1
: 1,2怎么推出3来的？
|
|
