tsy3602 : 帖个晚上考试的算法题，如果可能的话麻烦版主重发

悲剧的权限，我帖个我们今天晚上考试的一个算法题，给大家看看，如果可能的话麻烦版主重发下：
consider an n*n matrix M of integer numbers in which the elements in each row are sorted in ascending order and so are the elements in each column.
Check if a given number is in M.
求O(n)解法。

(这题我发过, 可以在网上搜杨氏矩阵)

大大这个不是发过吗？
下面好多人在讨论来着。。
ps NOI的孩子们伤不起 。。

O（n）的话，很简单。
从右上角（或者左下角）开始。
线性回扫，在那行找到第一个比key小的元素，然后在那一列找到第一个比key大的元素。
repeat until找到或者不能移动了。

不用线性扫的话，binary search，quad划分都能保证不比O（n）慢。

楼上搞NOI的？ 膜拜一下... 有前途的孩纸啊
PS 奔三的人看十几岁小孩的论文想破脑袋，你们伤不起。
burself 发表于 2011-11-1 06:04

    可别。。我是说楼主是啊楼主是。。我也奔三了光阴虚度啊 T.T