http://my.oschina.net/zangzy/blog/69103

楊氏矩陣問題

問題描述

如果一個矩陣每一行每一列都嚴(yán)格單調(diào)遞增，我們稱該矩陣為楊氏矩陣（Young Tableau）。對于楊氏矩陣(a[m][ n])，通常會涉及兩個問題：(1) 怎樣在楊氏矩陣中查找某個元素X？(2) 怎樣在楊氏矩陣找第k大的數(shù)？

解決方案

楊氏矩陣是一種非常巧妙的數(shù)據(jù)結(jié)構(gòu)，它既可以用來當(dāng)堆，又可以用來當(dāng)做平衡樹。?
(1) 問題1求解?
【方案一】?
<二分查找>?
對于楊氏矩陣，由于每行每列均是有序的，則可以于矩陣采用二分查找。具體方法是：?
對于當(dāng)前子矩陣a[i][j]~a[s][t]，中間元素為a[(i+s)/2][(j+t)/2]，如果a[(i+s)/2][(j+t) /2]==x，則找出該元素；如果a[(i+s)/2][(j+t)/2] > x，則在子矩陣a[i][j]~a[(i+s)/2][(j+t)/2]中查找；如果a[(i+s)/2][(j+t)/2] < x，則在三個子矩陣：a[i][(j+t)/2]~ a[(i+s)/2][t]，a[(i+s)/2][(j+t)/2]~ a[s][t]和a[(i+s)/2][j]~ a[s][ (j+t)/2]中查找。該算法的遞歸式為f(mn)=3f(mn/4)+O(1)，根據(jù)主定理知，時間復(fù)雜度為：O((mn)^(log4(3)))。?
【方案二】?
<類堆查找法>?
楊氏矩陣具有明顯的堆特征：從矩陣的右上角出發(fā)（從左下角出發(fā)思路類似），對于元素a[i][j]，如果a[i][j]==x，則找到元素x，直接返回； 如果a[i][j] > x，則向下移動，即繼續(xù)比較a[i+1][j]與x；如果a[i][j] < x，則向左移動，即繼續(xù)比較a[i][j-1]與x。該算法的時間復(fù)雜度是O(m+n)，代碼如下： bool find_in_YoungTableau(int** a, int m, int n, int x) {assert(a != NULL && m > 0 && n > 0);int row, col;row = 0;col = n-1;while(row <= m-1 && col >= 0) {if(a[row][col] == x)return true;else if(a[row][col] > x)col--;elserow++;}return false; } (2) 問題2求解?
【方案一】?
<小頂堆法>?
首先將a[0][0]加入小頂堆，然后每次從小頂堆中取出最小元素，并加入比該元素大且與之相鄰的兩個元素（對于a[0][0]，則需要加入a[0] [1]和a[1][0]），直到取出第k個元素，需要注意的是，需要采用額外空間記錄某個元素是否已經(jīng)加入到小頂堆以防止重復(fù)加入。?
【方案二】?
<二分枚舉+類堆查找>?
首先，二分枚舉找到一個數(shù)x，它比楊氏矩陣中k個數(shù)大；然后，利用類堆查找法找到剛好小于x的元素。該算法的時間復(fù)雜度為O((m+n)lg(mn))，但不需要額外存儲空間。代碼如下： int find_kth_in_YoungTableau(int** a, int m, int n, int k) {int low = a[0][0];int high = a[m-1][n-1];int order = 0;int mid = 0;do {mid = (low + high) >> 1;order = get_order(a, m, n, mid);if(order == k)break;else if(order > k)high = mid - 1;elselow = mid + 1;} while(1); //二分枚舉整，找出正好大于k的一個整數(shù) mid int row = 0;int col = n - 1;int ret = mid;//這個地方有些問題while(row <= m-1 && col >= 0) { //找出比mid小的最大數(shù)if(a[row][col] < mid) {//并且應(yīng)該考慮到矩陣中可能會存在巧好等于mid的數(shù)，然后就直接返回就好了ret = (a[row][col] > ret) ? a[row][col] : ret;row++;} else {col--;}}return ret; }//整數(shù)k在矩陣中的排名 int get_order(int** a, int m, int n, int k) {int row, col, order;row = 0;col = n-1;order = 0;while(row <= m-1 && col >= 0) {if(a[row][col] < k) {order += col + 1;row++;} else {col--;}}return order; }

總結(jié)

以上是生活随笔為你收集整理的杨氏矩阵以及扩展的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。