轉(zhuǎn):
一個(gè) m*n 的 Young 氏矩陣(Young tableau) 是一個(gè) m*n 的矩陣,其中每一行的數(shù)據(jù)都從左到右排序,每一列的數(shù)據(jù)都從上到下排序.Young 氏矩陣中可能會(huì)有一些 ∞ 數(shù)據(jù)項(xiàng),表示不存在的元素.所以,Young 氏矩陣可以用來存放 r<= mn 個(gè)有限的元素.
a).畫一個(gè)包含{9,16,3,2,4,8,5,14,12} 的4*4 的 Young 氏矩陣.b).給出一個(gè)在非空 m*n 的 Young 氏矩陣上實(shí)現(xiàn) EXTRACT-MIN 算法,使其運(yùn)行時(shí)間為O(m+n).
c).說明如何在O(m+n)時(shí)間內(nèi),將一個(gè)新元素手入到一個(gè)未滿的 m*n Young 氏矩陣中.
d).給出一個(gè)時(shí)間復(fù)雜度為 O(n^3) 的對 n*n Young 氏矩陣排序的算法.
e).給出一個(gè)運(yùn)行時(shí)間為O(m+n) 的算法,來決定一個(gè)給定的數(shù)是否存在于一個(gè)給定的 m*n 的 Young 氏矩陣當(dāng)中.
答
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的寫法.函數(shù)名即是返回值.
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]與最右下角元素交換, 然后移動(dòng)Young[1][1]處的元素至合適位置，即把它與右方或下方元素的比較,并與其中較小的一個(gè)交換.反復(fù)進(jìn)行直到它不大于它右方和下方的元素為止.
c). 類似堆的插入：先將待插入的元素 K 放在 Young[m][n], 然后比較 K 與它左方或上方元素的大小,并與其中較大的一個(gè)交換.反復(fù)進(jìn)行直到 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). 調(diào)用 n*n 次 EXTRACT_MIN 過程即可.
e). 總是于最右上角的元素X比較；
1）如果==X,結(jié)束；
2）如果比X小，那么元素只可能在前N-1列中；
3）如果比X大，那么元素只可能在后M-1行中；
Young 氏矩陣去掉一行或一列還是 Young 氏矩陣；
所以每次比較最少去掉一行或一列，這樣復(fù)雜度就是 O(m+n);