数据结构应用回望之杨氏矩阵
数据结构应用回顾之杨氏矩阵
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(""); } } }