Young氏矩阵问题及算法
百度某年的笔试题就考过Young氏矩阵的存在问题，所以这里把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 氏矩阵当中.
答
a). 2 3 4 5
8 9 12 14
16 ∞ ∞ ∞
∞ ∞ ∞ ∞
PS.该矩阵并不是唯一的.
b). (1)用递归的思想.在 Young 氏矩阵中，通过递归的解决(m-1)*n,或m*(n-1) 的子问题来求解.则有 T(m,n)=T(m-1,n) or T(m,n-1)+ O(1),显然,T=O(m+n).伪代码如下:
EXTRACT_MIN=Young[1][1]; //类似FORTRAN的写法.函数名即是返回值.
Young[1][1]= INFINITY;
ADJUST_TO_YOUNG(Young[1...m] [1...n]);
END
ADJUST_TO_YOUNG(Young[x...m] [y...n])
if(Young[x][y]==∞)
return;
if(Young[x+1][y]>Young[x][y+1])
swap(Young[x][y], Young[x][y+1]);
ADJUST_TO_YOUNG(Young[x...m][y+1...n]);
else
swap(Young[x][y], Young[x+1][y]);
ADJUST_TO_YOUNG(Young[x+1...m][y...n]);
END
(2)类似堆的删除：将Young[1][1]与最右下角元素交换, 然后移动Young[1][1]处的元素至合适位置，即把它与右方或下方元素的比较,并与其中较小的一个交换.反复进行直到它不大于它右方和下方的元素为止.
c). 类似堆的插入：先将待插入的元素 K 放在 Young[m][n], 然后比较 K 与它左方或上方元素的大小,并与其中较大的一个交换.反复进行直到 K 不小于它左方和上方的元素为止. 在这里,同样有,T(m,n)=T(m-1,n) or T(m,n-1)+ O(1),T=O(m+n).伪代码如下:
if(Young[m][n] < INFINITY) alert: 矩阵已满,无法插入!!
while(k<Young[m-1][n] or k<Young[m][n-1])
if(Young[m-1][n] >Young[m][n-1])
swap(k,Young[m-1][n]);
m=m-1;
else
swap(k,Young[m][n-1]);
n=n-1;
END
d). 调用 n*n 次 EXTRACT_MIN 过程即可.
e). 总是于最右上角的元素X比较；
1）如果==X,结束；
2）如果比X小，那么元素只可能在前N-1列中；
3）如果比X大，那么元素只可能在后M-1行中；
Young 氏矩阵去掉一行或一列还是 Young 氏矩阵；
所以每次比较最少去掉一行或一列，这样复杂度就是 O(m+n);
SEARCH (k,Young[1...m][1...n]) if (k < Young[1][1] or k > Young[m][n] return ”Not Found”;i = 1;
for (j=n; j > 0; –j)
if (k==Young[i][j]) return ”Found”, i, j.
else if (k > Young[i][j])for (; i <= m; ++i)
if (k==Young[i][j]) return ”Found”, i, j.
if (k < Young[i][j]) break;
if (i == m+1)
return ”Not Found”.
if (j == 0)
return ”Not Found”.
END
近期评论