数据结构应用回顾之杨氏矩阵

Young氏矩阵

   一个m*n的Young氏矩阵是一个m*n的矩阵，其中每一行的数据都从左到右排序，每一列的数据都从上到下排序。Young氏矩阵中会有一些∞数据项，表示不存在的元素。Young氏矩阵可以存放m*n个有限的数。常见Young氏矩阵的相关操作包括：

1、向一个不满的Young氏矩阵中插入一个元素x，并保持Young氏矩阵的性质

2、根据一个数组，构建一个m*n的Young氏矩阵

3、移除Young氏矩阵中最小的元素，并保持Young氏矩阵的性质

4、判断Young氏矩阵为空或满

5、使用n*n的Young氏矩阵来对n^2个数进行排序，运行时间复杂度为O(n^3)

6、在O(m+n)的时间复杂度内，找出Young氏矩阵中等于x的所有坐标

 

 

package com.fangming.dataStructure.BiTree;

public class YoungMatrix {

	public static void main(String[] args) {
		int[][] youngMatrix = createYoungMatrix(new int[] { 7, 2, 1, 4, 7, 8,
				9, 0, 3, 2, 1, 3, 5, 7, 8, 9 }, 4, 4);
		//removeMin(youngMatrix,4,4,0, 0);
		//removeMin(youngMatrix);
		//print(youngMatrix);
		//sort(youngMatrix);
		findAllDataNoRecurtion(youngMatrix,7);
	}
	
	//非递归方式移除最小的值
	public static void removeMin(int [][] youngMatrix){
		youngMatrix[0][0] = Integer.MAX_VALUE;
		YoungMatrixityDown(youngMatrix,0,0);
	}
	
	//杨氏矩阵的排序输出
	public static void sort(int [][] youngMatrix){
		while(youngMatrix[0][0] != Integer.MAX_VALUE) {
			System.out.print(youngMatrix[0][0] + ",");
			removeMin(youngMatrix);
		}
	}
	
	public static void findData(int [][] youngMatrix,int x){
		findData(youngMatrix,youngMatrix.length-1,0 ,x );
	}
	
	public static void findDataNoRecurtion(int [][] youngMatrix,int x){
		int i = youngMatrix.length-1;
		int j = 0;
		while(i >= 0 && j < youngMatrix[0].length ){
			if (youngMatrix[i][j] == x){
				System.out.println( "(" + i + "," + j + ")");
				return;
			}else if (x < youngMatrix[i][j]){
				i--;
			}else {
				j++;
			}
		}
	}
	
	public static void findAllDataNoRecurtion(int [][] youngMatrix,int x){
		int i = youngMatrix.length-1;
		int j = 0;
		while(i >= 0 && j < youngMatrix[0].length ){
			if (youngMatrix[i][j] == x){
				System.out.println( "(" + i + "," + j + ")");
				//往回找
				for(int k = i-1 ; k >=0 ; --k ){
					if (youngMatrix[k][j] == x){
						System.out.println( "(" + k + "," + j + ")");
					}
				}
				j++;
			}else if (x < youngMatrix[i][j]){
				i--;
			}else {
				j++;
			}
		}
	}
	
	//找出杨氏矩阵中存在的元素x,并输出x,y坐标
	public static void findData(int [][] youngMatrix,int m,int n ,int x){
		if (m >= 0 && n <youngMatrix.length){
			if (youngMatrix[m][n] == x){
				System.out.println( "(" + m + "," + n + ")");
				return;
			}else if (x < youngMatrix[m][n] ){
				findData(youngMatrix,m-1,n,x);
			}else {
				findData(youngMatrix,m,n + 1,x);
			}
		}
	}
	
	// 递归方式移除最小的值
	public static void removeMin(int[][] youngMatrix,int m,int n, int x, int y) {
		if (y + 1 < n && x+1 < m
				&& youngMatrix[x][y + 1] < youngMatrix[x + 1][y]) {
			youngMatrix[x][y] = youngMatrix[x][y + 1];
			removeMin(youngMatrix, m,n,x, y + 1);
		} else if (y + 1 < youngMatrix[0].length && x+1 < youngMatrix.length
				&& youngMatrix[x][y + 1] >= youngMatrix[x + 1][y]) {
			youngMatrix[x][y] = youngMatrix[x + 1][y];
			removeMin(youngMatrix,m,n, x + 1, y);
		} 
		if (x + 1 >= m) {
			for (int j = y; j < n - 1; ++j) {
				if (youngMatrix[x][j] != Integer.MAX_VALUE) {
					youngMatrix[x][j] = youngMatrix[x][j + 1];
				}
			}
			youngMatrix[x][n - 1] = Integer.MAX_VALUE;
		} 
		if (y + 1 >= n ) {
			for (int j = x; j < m - 1; ++j) {
				if (youngMatrix[j][y] != Integer.MAX_VALUE) {
					youngMatrix[j][y] = youngMatrix[j + 1][y];
				}
			}
			youngMatrix[m - 1][y] = Integer.MAX_VALUE;
		}
	}

	// 维持杨氏矩阵的性质
	public static void YoungMatrixityDown(int[][] data, int x, int y) {
		int smallestX = x;
		int smallestY = y;
		// 横坐标
		if (y + 1 < data[0].length && data[x][y + 1] < data[x][y]) {
			smallestY = y + 1;
			smallestX = x;
		}
		// 纵坐标
		if (x + 1 < data.length && data[x + 1][y] < data[smallestX][smallestY]) {
			smallestX = x + 1;
			smallestY = y;
		}
		if (x != smallestX || y != smallestY) {
			int temp = data[x][y];
			data[x][y] = data[smallestX][smallestY];
			data[smallestX][smallestY] = temp;
			YoungMatrixityDown(data, smallestX, smallestY);
		}
	}

	// 维持杨氏矩阵的性质
	public static void YoungMatrixityUp(int[][] data, int x, int y) {
		int smallestX = x;
		int smallestY = y;
		// 横坐标
		if (y - 1 >= 0 && data[x][y - 1] > data[x][y]) {
			smallestY = y - 1;
			smallestX = x;
		}
		// 纵坐标
		if (x - 1 >= 0 && data[x - 1][y] > data[smallestX][smallestY]) {
			smallestX = x - 1;
			smallestY = y;
		}
		if (x != smallestX || y != smallestY) {
			int temp = data[x][y];
			data[x][y] = data[smallestX][smallestY];
			data[smallestX][smallestY] = temp;
			YoungMatrixityUp(data, smallestX, smallestY);
		}
	}

	// 根据数组生成杨氏矩阵
	public static int[][] createYoungMatrix(int[] data, int m, int n) {
		int[][] result = new int[m][n];
		int length = data.length;
		assert length <= m * n;
		//init 
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				result[i][j] = Integer.MAX_VALUE;
			}
		}
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (i * n + j < length) {
					result[i][j] = data[i * n + j];
				}
				YoungMatrixityUp(result, i, j);
			}
		}
		print(result);
		return result;
	}

	private static void print(int[][] data) {
		int m = data.length;
		int n = data[0].length;
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				System.out.print(data[i][j]);
				System.out.print(" ");
			}
			System.out.println("");
		}
	}
}