首页 > 代码库 > Young氏矩阵
Young氏矩阵
一个 m x n 的Young氏矩阵是指，每一行数据都是从左到右排好序，每一列的数据也都是从上到下排好序。其中也可能存在一些INF的数据，表示不存在的元素，一个mxn的Young氏矩阵最多用来存放 r <= mn个元素。
详细见《算导》P.83
Young氏矩阵类似于堆的结构，主要实现的API包括以下：
1. void insert(int x)
功能：将一个元素x插入到矩阵中,复杂度O(m+n)
算法过程：
1) 判断矩阵是否为Full
2) 如果不为Full，插入元素到矩阵的右下角(row, col)位置，然后进行swim(row, col)将元素移动到合适位置。
2. int getMin()
功能：返回矩阵中的最小值,复杂度O(1)
算法过程：
1) 判断矩阵是否为Empty
2) 直接返回mat[0][0].左上角元素，依据矩阵的性质
3. int delMin()
功能：返回矩阵中的最小值，并把它从矩阵中删除,复杂度O(m+n)
算法过程：
1) 判断矩阵是否为Empty
2) 暂存mat[0][0]元素用于返回，把矩阵最右下角的元素放到mat[0][0]，使用sink(0, 0)进行下沉调整元素到合适位置
4. bool seach(int x)
功能：判断矩阵是否存在元素x,复杂度O(m+n)
算法过程：
版本1：通过递归的方式，比较当前mat[x][y] 和 key的关系，将划分到是否需要在(m-1)x(n)子矩阵和mx(n-1)子矩阵进行递归查找
版本2：初始位置为矩阵右上角，如果当前元素大于key，向左移动，如果当前元素小于key向下移动。
5. void sort()
功能：对矩阵元素进行排序，对矩阵执行元素个数次的delMin()操作就可以得到排序结果。复杂度O(n*m*(n+m))
辅助函数:
==两个函数的实现与实现堆的swim和sink操作思想完全一样==
void swim(int i, int j)
功能：对(i, j)位置元素进行上浮操作，与(i-1, j) 和 (i, j-1)位置的元素进行比较，与他们之间的最大值进行交换
void sink(int i, int j)
功能：对(i, j)位置元素进行下沉操作，与(i+1, j) 和 (i, j+1)位置的元素进行比较， 与他们之间的最小值进行交换
完整代码如下：
const int INF = 0x3fffffff;class YoungMatrix {public: YoungMatrix(int row, int col); // constructor ~YoungMatrix(); // destructor void insert(int x); // insert a element int delMin(); // delete and return the minimal element bool search(int x, int version = 1); // search a element int getMin(); // return the minimal element // sort(); // 调用 n*n delMin()得到结果n*n*(n+n) O(n^3) // print the matrix void printMatrix() { for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) cout << mat[i][j] << "\t"; cout << endl; } cout << endl; } /*** auxiliary function ***/private: void swim(int i, int j); // swim the element at (i, j), 从右下角上升到左上角 void sink(int i, int j); // sink the element at (i, j), 从左上角下沉到右下角 bool searchHelp1(int x, int y, int key); // recursive function to search the element, divide the problem into sub-matrix (m, n-1) and (m-1, n) bool searchHelp2(int key); // init the position in (0, col-1). like go down the stairs from right to leftprivate: int **mat; int row, col; int num;};YoungMatrix::YoungMatrix(int row, int col) { this->num = 0; this->row = row; this->col = col; mat = new int*[row]; for (int i = 0; i < row; i++) mat[i] = new int[col]; for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) mat[i][j] = INF;}YoungMatrix::~YoungMatrix() { for (int i = 0; i < row; i++) delete[] mat[i]; delete[] mat;}void YoungMatrix::swim(int i, int j) { while (true) { int v = mat[i][j], p = -1; if (i - 1 >= 0 && v < mat[i - 1][j]) { v = mat[i - 1][j], p = 0; } if (j - 1 >= 0 && v < mat[i][j - 1]) { v = mat[i][j - 1]; p = 1; } if (p == -1) break; if (p == 0) { swap(mat[i - 1][j], mat[i][j]); i -= 1; } else { swap(mat[i][j - 1], mat[i][j]); j -= 1; } }}void YoungMatrix::sink(int i, int j) { while (true) { int v = mat[i][j], p = -1; if (i + 1 < row && v > mat[i + 1][j]) { v = mat[i + 1][j], p = 0; } if (j + 1 < col && v > mat[i][j + 1]) { v = mat[i][j + 1]; p = 1; } if (p == -1) break; if (p == 0) { swap(mat[i + 1][j], mat[i][j]); i += 1; } else { swap(mat[i][j + 1], mat[i][j]); j += 1; } }}void YoungMatrix::insert(int x) { // is full? if (num == col * row) { cerr << "Error: the matrix is full" << endl; return; } // put at the last position this->num++; int i = row - 1, j = col - 1; mat[i][j] = x; swim(i, j);}int YoungMatrix::getMin() { if (this->num > 0) return mat[0][0]; else { cerr << "Error: The matrix is empty" << endl; return -1; }}int YoungMatrix::delMin() { if (this->num <= 0) { cerr << "Error: The matrix is empty" << endl; return -1; } else { int ret = mat[0][0]; mat[0][0] = mat[row - 1][col - 1]; this->num--; sink(0, 0); return ret; }}bool YoungMatrix::search(int x, int version) { if (this->num <= 0) return false; if (version == 1) { return searchHelp1(0, 0, x); } else { return searchHelp2(x); }}bool YoungMatrix::searchHelp1(int x, int y, int key) { if (x >= row || y >= col) return false; if (mat[x][y] < key) return searchHelp1(x + 1, y, key) || searchHelp1(x, y + 1, key); else if (mat[x][y] > key) return false; else return true;}bool YoungMatrix::searchHelp2(int key) { int i = 0, j = col - 1; while (true) { if (i >= row || j >= col) return false; if (mat[i][j] == key) return true; else if (mat[i][j] < key) i++; else if (mat[i][j] > key) j--; }}
测试代码：
#include "YoungMatrix.h"using namespace std;int a[] = { 9, 16, 3, 2, 4, 8, 5, 14, 12 };int main(int argc, char** argv) { YoungMatrix ym(4,4); int e; for (int i = 0; i < 9; i++) { ym.insert(a[i]); } ym.printMatrix(); cout << "search result: " << ym.search(2, 2) << endl; cout << ym.delMin() << endl; cout << "search result: " << ym.search(2, 2) << endl; ym.printMatrix(); return 0;}
Young氏矩阵