关于Young氏矩阵中存在性问题

在《算法导论》一书里，有这样一个课后思考题：

一个 m*n 的 Young 氏矩阵(Young tableau) 是一个 m*n 的矩阵，其中每一行的数据都从左到右排序，第一列的数据都从上到下排序。 Young氏矩阵中可能会有一些∞数据项，表示不存在的元素。所以，Young氏矩阵可以用来存放 r <= mn 个有限的元素。

a. 画一个包含{9,16,3,2,4,8,5,14,12} 的4*4 的Young氏矩阵

b. 给出一个在非空 m*n 的Young氏矩阵上实现 EXTRACT-MIN 算法，使其运行时间为O(m+n)

c. 说明如何在O(m+n)时间内，将一个新元素手入到一个未满的 m*n Young氏矩阵中

d. 给出一个时间复杂度为 O(n^3) 的对 n*n Young氏矩阵排序的算法

e. 给出一个运行时间为O(m+n) 的算法，来决定一个给定的数是否存在于一个给定的 m*n的 Young氏矩阵当中

题目主要提到杨氏矩阵的概念，比如下面就是一个简单的杨氏矩阵：

1 2 3  4
4 6 8  9
5 7 9  10
6 9 10 12

当然这个杨氏矩阵里没有空，也就是没有∞元素。该矩阵的特点也很明确，就是越靠近右下角，数值越大，而越靠近左上角，数值越小。

之所以把这个题目翻出来看，是因为前不久参加了百度上海研究院2010年实习生招聘笔试，在该笔试中就有这么一道题，它与上题中的第（e）问非常相似：

给定如下的n*n的数字矩阵，每行从左到右是严格递增，每列的数据也是严格递增

1 2 5
3 4 6
4 8 9

现在要求设计一个算法，给定一个数k判断出k是否在这个矩阵中。描述算法并且给出时间复杂度（不考虑载入矩阵的消耗）

不难看出百度的笔试题也是讨论杨氏矩阵中的元素存在性问题，不同的是百度试题里给出的是一个简化的杨氏矩阵，即该矩阵是n*n的方阵，同时该矩阵中不会有∞这样的空元素。两相对比，你可能马上就会想到答案是O(n+n)即O(n)，尽管《算法导论》是很权威的书，不过在没有完全理解的情况下，不敢苟同，因为我思考了很多，也没有想到一个速度达到O(n)的算法。我尝试去寻找《算法导论》的课后答案，不过很遗憾偏偏这题没有提供答案。网上倒是有相关答案：

SEARCH(k,Young[x...m][y...n])
    if(k<Young[x][y] or k>Young[m][n])
        return "NotFound";
    if(k==Young[x][y])
        return "Found",x,y;
    if(k<Young[x+1][y])
        SEARCH(k,Young[x...x][y+1...n]
    else
        SEARCH(k,Young[x+1...m][y...n]
END

这是一个递归算法，我觉得有问题的就是

if(k<Young[x+1][y])
        ...
    else
        ...

这一句，让我来举例说明吧，假如我们有如下一个矩阵：

1 3 5 6
2 5 6 7
4 6 7 8
6 7 8 9

如果说我们要判断2是否存在于该杨氏矩阵中，从上面的解法来看，我们先将2与Young[x+1][y]即3，进行比较，结果2<3，那么2肯定比子矩阵

3 5 6
5 6 7
6 7 8
7 8 9

中的任何一个数都要小，所以2只可能存在于Young[x...x][y+1...n]即

2
4
6

中，最后使用一下二分查找就能马上证明2存在于该矩阵中。

然而，假如我们要查找4，从上面提到的算法来看，4比Young[x+1][y]即3要大，算法就武断地进入else分支，认定了4绝对不会在Young[x...x][y+1...n]中出现，不过很遗憾4恰好在

2
4
6

中出现了。如果以上算法真是《算法导论》一书的“官方”答案的话，我个人觉得是解释不通的。

我能想到最好的办法，其速度也只能达到O(n*logn)，以下是我针对百度笔试题的解法：

先举个例子，假设矩阵如下：

 1  3  4  5  7 10
 2  4  7 12 13 15
 4  5  8 13 14 16
 6  8 10 15 17 19
 8 10 12 16 18 21
11 12 15 19 20 22

而要查找的数为x=9。

1. 如果x比左上角的数小，或者比右下角的数大，则查找失败。现在1<9<22，继续查找。

2. 将x与左下角的数m进行比较，如果相等则查找成功;如果x小于m，则在第一列上进行对x的二分查找，查找到则查找成功，否则返回查找的最终位置;如果x大于m，则在最后一行上进行二分查找，查找到则查找成功，否则返回查找结束的最后位置。这里x=9<11,所以在第一列（即1 2 4 6 8 11）上进行二分查找，该列中没有9,则返回二分查找的最终位置8与11之间，然后剥去第一列，剥去大于x的列，即列11 12 15 19 20 22，将搜索矩阵缩小规模，即：

  3  4  5  7 10
  4  7 12 13 15
  5  8 13 14 16
  8 10 15 17 19
 10 12 16 18 21

问题变成在如上矩阵中查找x=9的问题了，递归进行如下步骤。

接着矩阵规模再次缩小到：

   4  5  7 10
   7 12 13 15
   8 13 14 16
  10 15 17 19

再进行以步骤1与2,矩阵规模缩小到：

   5  7 10
  12 13 15
  13 14 16

再进行以步骤1与2,矩阵规模缩小到：

  7 10

再进行以步骤1与2,没的查找到x=9,所以最终查找失败!

当然以上是一种比较坏的情况。最坏情况下是一层一层的剥离，其时间复杂度为n*logn。

不过，个人能力有限，可能真有如《算法导论》一书说到的O(n)的时间复杂度算法，希望有想法的朋友能给我留言。