c***g
发帖数: 472 | 1 Given a matrix in which each row and each column is sorted, write a method
to find an element in it.
上面给的算法是，从最右上角开始找起，然后每次去掉一行或者一列。
我有如下疑问
1） 如果从左下角开始，也是对的吧，每次去掉一行或者一列；
2） 这个算法的时间复杂度应该是N*M吧？
3） 可以更加优化么？ 每次找的时候，用二分发找到那个数所在的区间，就是恰好找
到一个大于它的，一个小于它的，这样时间复杂度不就是(lgM * lgN)？
|
s******n
发帖数: 3946 | 2 1 对
2 怎么会是N*M，应该是N+M
3 两分法只能优化第一步，没什么作用 |
c***g
发帖数: 472 | 3 2） 嗯， N + M, typo
3）
为什么只对第一步有用呢
1 2 3 4 5 6
7 8 9 22 21 24
13 14 15 24 27 28
19 20 21 25 29 29
25 26 27 28 29 30
31 32 33 34 35 36
假设找22， 从最左下角开始找起，发现22介于19和25中间， 这样最后两行都可以扔掉了
然后发现22 介于21 和25之间，这样左边三列都可以扔掉
当很大的时候，每次二分法找这个区间应该比挨个找快啊。
【在 s******n 的大作中提到】
: 1 对
: 2 怎么会是N*M，应该是N+M
: 3 两分法只能优化第一步，没什么作用
|
C***U
发帖数: 2406 | 4 你用二分法找，反而需要更多时间
掉了
【在 c***g 的大作中提到】
: 2） 嗯， N + M, typo
: 3）
: 为什么只对第一步有用呢
: 1 2 3 4 5 6
: 7 8 9 22 21 24
: 13 14 15 24 27 28
: 19 20 21 25 29 29
: 25 26 27 28 29 30
: 31 32 33 34 35 36
: 假设找22， 从最左下角开始找起，发现22介于19和25中间， 这样最后两行都可以扔掉了
|
C***U
发帖数: 2406 | 5 举个例子
1 300 400 500
2 400 500 600
3 500 600 700
4 1000 2000 3000
如果你要找501
一直用二分法 用的时间比直接比较的多
这些数字随便取得
【在 C***U 的大作中提到】
: 你用二分法找，反而需要更多时间
:
: 掉了
|
r*****b
发帖数: 310 | 6 It is not guarnatted that all A[i][j] >= A[i-1][j]
For instance,
28, 29, 31, 36
33, 38, 39, 48
33, 44, 51, 56
41, 44, 52, 59
If you try to search 38, the binary search may not give the right answer.
Here is a post on this:
http://basicalgos.blogspot.com/2012/03/14-find-element-in-sorte
掉了
【在 c***g 的大作中提到】
: 2） 嗯， N + M, typo
: 3）
: 为什么只对第一步有用呢
: 1 2 3 4 5 6
: 7 8 9 22 21 24
: 13 14 15 24 27 28
: 19 20 21 25 29 29
: 25 26 27 28 29 30
: 31 32 33 34 35 36
: 假设找22， 从最左下角开始找起，发现22介于19和25中间， 这样最后两行都可以扔掉了
|
c***g
发帖数: 472 | 7 It is not guarnatted that all A[i][j] >= A[i-1][j]
没看明白，不是sorted么？
【在 r*****b 的大作中提到】
: It is not guarnatted that all A[i][j] >= A[i-1][j]
: For instance,
: 28, 29, 31, 36
: 33, 38, 39, 48
: 33, 44, 51, 56
: 41, 44, 52, 59
: If you try to search 38, the binary search may not give the right answer.
: Here is a post on this:
: http://basicalgos.blogspot.com/2012/03/14-find-element-in-sorte
:
|
Q**a
发帖数: 406 | 8 说一下我的想法，请指正
lz的方法是可行的，唯一的问题是cost estimation比较困难，很难说比原始方法更优
我倾向于认为lz的方法更慢一点，模糊的感觉如下，欢迎按编号批驳
1. 二分查找隐含的假设是“所查找的元素在有序表中的位置服从均匀分布“
2. 而类似的合理假设是在本题的矩阵中所查找的目标元素可能的位置同样服从均匀分布
3. 在绘制阶梯的过程中，移除部分行列后目标元素的投影不再服从均匀分布
4. 使用二分查找的效率逐渐降低
另外在lz的启发下我想到这个办法，可能会稍微好一点：在绘制阶梯的过程中第i步走2
^i
【在 c***g 的大作中提到】
: It is not guarnatted that all A[i][j] >= A[i-1][j]
: 没看明白，不是sorted么？
|
c***g
发帖数: 472 | 9 Given a matrix in which each row and each column is sorted, write a method
to find an element in it.
上面给的算法是，从最右上角开始找起，然后每次去掉一行或者一列。
我有如下疑问
1） 如果从左下角开始，也是对的吧，每次去掉一行或者一列；
2） 这个算法的时间复杂度应该是N*M吧？
3） 可以更加优化么？ 每次找的时候，用二分发找到那个数所在的区间，就是恰好找
到一个大于它的，一个小于它的，这样时间复杂度不就是(lgM * lgN)？
|
s******n
发帖数: 3946 | 10 1 对
2 怎么会是N*M，应该是N+M
3 两分法只能优化第一步，没什么作用 |
|
|
c***g
发帖数: 472 | 11 2） 嗯， N + M, typo
3）
为什么只对第一步有用呢
1 2 3 4 5 6
7 8 9 22 21 24
13 14 15 24 27 28
19 20 21 25 29 29
25 26 27 28 29 30
31 32 33 34 35 36
假设找22， 从最左下角开始找起，发现22介于19和25中间， 这样最后两行都可以扔掉了
然后发现22 介于21 和25之间，这样左边三列都可以扔掉
当很大的时候，每次二分法找这个区间应该比挨个找快啊。
【在 s******n 的大作中提到】
: 1 对
: 2 怎么会是N*M，应该是N+M
: 3 两分法只能优化第一步，没什么作用
|
C***U
发帖数: 2406 | 12 你用二分法找，反而需要更多时间
掉了
【在 c***g 的大作中提到】
: 2） 嗯， N + M, typo
: 3）
: 为什么只对第一步有用呢
: 1 2 3 4 5 6
: 7 8 9 22 21 24
: 13 14 15 24 27 28
: 19 20 21 25 29 29
: 25 26 27 28 29 30
: 31 32 33 34 35 36
: 假设找22， 从最左下角开始找起，发现22介于19和25中间， 这样最后两行都可以扔掉了
|
C***U
发帖数: 2406 | 13 举个例子
1 300 400 500
2 400 500 600
3 500 600 700
4 1000 2000 3000
如果你要找501
一直用二分法 用的时间比直接比较的多
这些数字随便取得
【在 C***U 的大作中提到】
: 你用二分法找，反而需要更多时间
:
: 掉了
|
r*****b
发帖数: 310 | 14 It is not guarnatted that all A[i][j] >= A[i-1][j]
For instance,
28, 29, 31, 36
33, 38, 39, 48
33, 44, 51, 56
41, 44, 52, 59
If you try to search 38, the binary search may not give the right answer.
Here is a post on this:
http://basicalgos.blogspot.com/2012/03/14-find-element-in-sorte
掉了
【在 c***g 的大作中提到】
: 2） 嗯， N + M, typo
: 3）
: 为什么只对第一步有用呢
: 1 2 3 4 5 6
: 7 8 9 22 21 24
: 13 14 15 24 27 28
: 19 20 21 25 29 29
: 25 26 27 28 29 30
: 31 32 33 34 35 36
: 假设找22， 从最左下角开始找起，发现22介于19和25中间， 这样最后两行都可以扔掉了
|
c***g
发帖数: 472 | 15 It is not guarnatted that all A[i][j] >= A[i-1][j]
没看明白，不是sorted么？
【在 r*****b 的大作中提到】
: It is not guarnatted that all A[i][j] >= A[i-1][j]
: For instance,
: 28, 29, 31, 36
: 33, 38, 39, 48
: 33, 44, 51, 56
: 41, 44, 52, 59
: If you try to search 38, the binary search may not give the right answer.
: Here is a post on this:
: http://basicalgos.blogspot.com/2012/03/14-find-element-in-sorte
:
|
Q**a
发帖数: 406 | 16 说一下我的想法，请指正
lz的方法是可行的，唯一的问题是cost estimation比较困难，很难说比原始方法更优
我倾向于认为lz的方法更慢一点，模糊的感觉如下，欢迎按编号批驳
1. 二分查找隐含的假设是“所查找的元素在有序表中的位置服从均匀分布“
2. 而类似的合理假设是在本题的矩阵中所查找的目标元素可能的位置同样服从均匀分布
3. 在绘制阶梯的过程中，移除部分行列后目标元素的投影不再服从均匀分布
4. 使用二分查找的效率逐渐降低
另外在lz的启发下我想到这个办法，可能会稍微好一点：在绘制阶梯的过程中第i步走2
^i
【在 c***g 的大作中提到】
: It is not guarnatted that all A[i][j] >= A[i-1][j]
: 没看明白，不是sorted么？
|
z******t
发帖数: 59 | 17 关于二分法，下面一个博客的解法不错：
http://blog.csdn.net/expp/article/details/7008972
【在 C***U 的大作中提到】
: 你用二分法找，反而需要更多时间
:
: 掉了
|
s*******s
发帖数: 27 | 18 那个博客上面的解法有个假设不对：对角线的元素也是排好序的
给出的题目完全不能推出这样的假设。例如：
4 5
9 11
也可以：
4 10
9 11
【在 z******t 的大作中提到】
: 关于二分法，下面一个博客的解法不错：
: http://blog.csdn.net/expp/article/details/7008972
|
z******t
发帖数: 59 | 19 博客中的对角线单指从左上角到右下角的对角线。
【在 s*******s 的大作中提到】
: 那个博客上面的解法有个假设不对：对角线的元素也是排好序的
: 给出的题目完全不能推出这样的假设。例如：
: 4 5
: 9 11
: 也可以：
: 4 10
: 9 11
|
i**********e
发帖数: 1145 | 20 这道题经典解法（Step-wise linear search, 也就是 lz 的解法） 是 O(N+M)，不是
O(N*M). 可以选择从左下角 或者右上角 都可以。
网上已经列出五种解法 并一起以真实数据比较算法速度。发现竟然 Improved Binary
partition （利用二分） 的算法是最快的。但是这个算法的复杂度非常难证明，如果
有人可以证明出来，我愿意发完我所有包子给他。
Binary Search: 31.62s
Diagonal Binary Search: 32.46s
Step-wise Linear Search: 10.71s
Quad Partition: 17.33s
Binary Partition: 10.93s
Improved Binary Partition: 6.56s
http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part |
|
|
C***U
发帖数: 2406 | 21 楼主说的二分发和你发的二分发不是同一个。。。
要么就是我理解错楼主的意思了。。。。
【在 z******t 的大作中提到】
: 关于二分法，下面一个博客的解法不错：
: http://blog.csdn.net/expp/article/details/7008972
|
i**********e
发帖数: 1145 | 22 哦，楼主的binarysearch的确是不同一个。
我之前说的binarysearch跟这里是同个思路：http://blog.csdn.net/expp/article/details/7008972
这个绝对要比 O(N log N) 还要快
【在 C***U 的大作中提到】
: 楼主说的二分发和你发的二分发不是同一个。。。
: 要么就是我理解错楼主的意思了。。。。
|
i**********e
发帖数: 1145 | 23 恩，认同。
这是worst case，每次只能删除一行或者一列。
比 O(N+M) 那个解法要慢，因为还要花时间 binary search。
楼主的binary search解法的复杂度是 O(N log (N)). （如果是 NxN 的矩阵的话）
【在 C***U 的大作中提到】
: 举个例子
: 1 300 400 500
: 2 400 500 600
: 3 500 600 700
: 4 1000 2000 3000
: 如果你要找501
: 一直用二分法 用的时间比直接比较的多
: 这些数字随便取得
|
H****r
发帖数: 2801 | 24 这个问题有人发了文章：
http://www.sciencedirect.com/science/article/pii/S0304397597000
在M==N时O(N), 一般情况下O(M * Log(2N / M))
细节好像比较复杂
是
Binary
【在 i**********e 的大作中提到】
: 这道题经典解法（Step-wise linear search, 也就是 lz 的解法） 是 O(N+M)，不是
: O(N*M). 可以选择从左下角 或者右上角 都可以。
: 网上已经列出五种解法 并一起以真实数据比较算法速度。发现竟然 Improved Binary
: partition （利用二分） 的算法是最快的。但是这个算法的复杂度非常难证明，如果
: 有人可以证明出来，我愿意发完我所有包子给他。
: Binary Search: 31.62s
: Diagonal Binary Search: 32.46s
: Step-wise Linear Search: 10.71s
: Quad Partition: 17.33s
: Binary Partition: 10.93s
|
H****r
发帖数: 2801 | 25 Google "Optimal algorithms for generalized searching in sorted matrices",
there's some pdf on this.
【在 i**********e 的大作中提到】
: 恩，认同。
: 这是worst case，每次只能删除一行或者一列。
: 比 O(N+M) 那个解法要慢，因为还要花时间 binary search。
: 楼主的binary search解法的复杂度是 O(N log (N)). （如果是 NxN 的矩阵的话）
|
