思考题6-3（Young氏矩阵）在一个$m\times n$的Young氏矩阵（Young tableau）中，每一行的数据都是从左到右排序的，每一列的数据都是从上到下排列的。Young氏矩阵中也会存在一些为 $\infty$ 的数据项，表示那些不存在的数据。因此，Young氏矩阵可以用来村出$r \leq mn$个有限的数。
a. 画出一个包含元素$\{9，16，3，2，4，8，5，14，12\}$的$4 \times 4$Young氏矩阵。
第一题比较简单，只要满足插入和每行每列都是非递减就行。
下面示例：
采用不同规则最终效果不同，只要满足其定义即可。
在后面的实现中我们为了简化边界检查，我们实际的矩阵实现行数和列数要比实际大2，Y的存储位置为$[1,1]$到$[M,N]$。
$4 \times 4$的Young氏矩阵的实际存储空间。
采取这种方案，当达到边界时，不会越界。
b. 对于一个$m \times n$的Young氏矩阵来说，请证明：如果$Y[1,1]=\infty$，则$Y$为空；如果$Y[m,n]< \infty$，则$Y$为满（即包含$mn$个元素）。
这道题比较简单，根据定义就可以快速得出。
证明：根据Young氏矩阵的定义，$Y[i,j] \leq Y[i+k1,j+k2]，\forall i,i+k1 \leq m$ 且 $j,j+k2 \leq n$。即$Y[1,1]$为矩阵的最小值，$Y[m,n]$为最大值。
如果$Y[1,1]=\infty$，则矩阵其他元素均为$\infty$，即为空。若$Y[m,n]< \infty$，则其他元素均小于$\infty$，故$Y$为满。
c. 请给出一个在$m \times n$ Young氏矩阵上时间复杂度为$O(m+n)$的EXTRACT-MIN的算法实现。你的算法可以考虑使用一个递归过程，它把一个规模为$m \times n$的问题分解为规模为$(m-1) \times n$或$m \times (n-1)$的子问题（提示：考虑使用MAX-HEAPFY）。这里，定义T(p)用来表示在任意$m \times n$的Young氏矩阵上的时间复杂度，其中$p = m+n$。给出并求解$T(p)$的递归表达式，其结果为$O(m+n)$。
这个实现上也比较简单。如下：
- 在$Y$非空时，将$Y[1,1]$用$\infty$替换
然后重新调整$\infty$的位置，记当前位置在$Y[i,j]$，让其满足定义。
- 取其下面元素$Y[i+1,j]$和右边元素$Y[i,j+1]$的最小值$mix$，若$min \neq \infty$交换它和$\infty$的位置。
- 当达到矩阵边界，或$min = \infty$，此时结束。
下面是伪代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19extractMin(Y)
if(!Y.empty())//非空
Y[1][1] = INF;//第一个元素置为INF
MinFixup(Y,Loc{1,1});//调整
MinFixup(Young,loc)
t = Y[loc.x][loc.y]
do
if(Y[loc.x][loc.y+1] < Y[loc.x+1][loc.y])//获取下方和右边小的数的位置
small = {loc.x,loc.y+1}
else
small = {loc.x+1,loc.y}
if(Y[small.x][small.y] < t)
Y[loc.x][loc.y] = Y[small.x][small.y]
loc = small
else
break
while(true)
Y[loc.x][loc.y] = t
该过程相当于一个棋子从左上角向右下方行走，每次交换后$i=i+1$或$j=j+1$，最多交换$m+n$次，总是时间复杂度为$O(m+m)$。
d. 是说明如何在$O(m+n)$的时间内，将一个元素插入到一个未满的$m \times n$的Young氏矩阵中。
类似二叉堆的插入过程，我们将新的元素放置在矩阵的最后一个位置$Y[m,n]$，类似题目c相反，让它与上面的元素$Y[m-1,n]$或左边的元素$Y[m,n-1]$比较，取它们的最大值$max$，若$max\leq Y[m,n]$，那么此时满足，否则，取用$max$与它交换。直到达到达到边界或满足Young氏矩阵的定义。
下面是伪代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19insert(Y,x)
if(!Y.full())
Y[M][N] = x
MaxFixup(Loc{M,N});
MaxFixup(Y,loc)
t = Y[loc.x][loc.y]
do
if(Y[loc.x][loc.y-1] < Y[loc.x-1][loc.y])
lager = {loc.x,loc.y-1}
else
small = {loc.x-1,loc.y}
if(Y[lager.x][lager.y] > t)
Y[loc.x][loc.y] = Y[lager.x][lager.y]
loc = lager
else
break
while(true)
Y[loc.x][loc.y] = t
e. 在不用其他排序算法的情况下，是说明如何利用一个$n \times n$的Young氏矩阵在$O(n^3)$时间内将$n^2$个数进行排列。
将$n \times n$个元素插入Young氏矩阵中，花费$O(n^3)$，然后将他们意义取出即可，也是花费$O(n^3)$。故总的时间复杂度为$O(n^3)$。
f. 设计一个时间复杂度为$O(m+n)$的算法，它可以用来判断一个给定的数是否存储在$m \times n$的Young氏矩阵内。
查找一个数$x$，我们可以从左下角或右上角开始搜索。不能从左上角或右下角进行，例如左上角来说，当我们查找点元素大于$Y[1,1]$时，若往右或下均是大于$x$时，我们不知道往那个方向，有可能选择方向错误后，后面需要回过头来找尝试另一方向，花费额外时间。
但是如果我们从左下角开始查找，如果$x < Y[m,1]$，那么我们往上继续查找，若$X > T[m,1]$，那么我们往右边查找。这样可以在$O(m+n)$时间内完成。当然，从右上角开始也是一样的效果。
下面从左下角查找的伪代码：1
2
3
4
5
6
7
8
9
10search(Y,t)//查找t
x = M,y=1
while(Y[x][y] != INF && Y[x][y] != -INF)//未到达边界
if(Y[x][y] == t)
return true
else if(t < Y[x][y])
x = x + 1
else
y = y - 1
return false
代码实现
1 |
|