Young氏矩阵问题及算法

Posted by 冰河 at 17:48 Add comments 7,145 Views
042011

百度某年的笔试题就考过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...m] [1...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).伪代码如下:

INSERT(k,Young[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);

Young 氏矩阵的相关算法 - 心如止水 - 学习心得SEARCH (k,Young[1...m][1...n])
Young 氏矩阵的相关算法 - 心如止水 - 学习心得 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.
Young 氏矩阵的相关算法 - 心如止水 - 学习心得 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”.
Young 氏矩阵的相关算法 - 心如止水 - 学习心得END

相关日志

Leave a Reply

(required)

(required)

click to change(必须)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Protected by WP Anti Spam
© 2009 - 2018 冰河的博客