Matrix Comparison algorithm
Posted
by SysAdmin
on Stack Overflow
See other posts from Stack Overflow
or by SysAdmin
Published on 2010-05-07T05:34:58Z
Indexed on
2010/05/07
5:38 UTC
Read the original article
Hit count: 334
If you have 2 Matrices of dimensions N*M. what is the best way to get the difference Rect?
Example:
2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3
2 3 4 5 4 3 2 3 <---> 2 3 2 3 2 3 2 3
2 3 4 5 2 3 2 3 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3
|
|
\ /
Rect([2,2] , [3,4])
4 5 4
4 5 2-> A (2 x 3 Matrix)
The best I could think of is to scan from Top-Left hit the point where there is difference. Then scan from Bottom Right and hit the point where there is a difference.
But In worst case, this is O(N*M). is there a better efficient algorithm?
© Stack Overflow or respective owner
