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(""); } } }
相关推荐
ACM必会-杨氏矩阵题解分析.zip 是一个压缩文件,包含了关于杨氏矩阵问题的详细题解和代码实现。该资源旨在帮助参加ACM竞赛的选手更好地理解杨氏矩阵问题,并提供相应的解决方案和代码示例。 内容概要: 该压缩文件...
本文实例为大家分享了python实现杨氏矩阵查找的具体代码,供大家参考,具体内容如下 问题描述: 在一个m行n列二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数...
使用纤维和基体或给定的数据来定义复合层,然后铺设层压板。 使用经典层压理论计算每一层的应力和应变分布。 选择合适的失效标准来检查给定负载下层压板的强度。 显示准确的计算结果信息,显示应力应变分布图;显示...
杨氏矩阵查找的JS代码,需要的朋友可以参考一下
杨氏模量实验报告数据.doc
*【重要:请更改Fe_sigma值,以产生分布,默认是零】*在结构力学中,常常假定材料是均质的,单一域内使用相同材料属性来做相应的结构分析。然而,实际材料很难做到完全均质。在这个案例中,将考察对一个平板简单拉伸...
大学物理实验杨氏模量的处理数据模板。。。。
用拉伸法测金属丝的杨氏模量数据及其数据处理讲课讲稿.pdf用拉伸法测金属丝的杨氏模量数据及其数据处理讲课讲稿.pdf用拉伸法测金属丝的杨氏模量数据及其数据处理讲课讲稿.pdf用拉伸法测金属丝的杨氏模量数据及其数据...
#资源达人分享计划#
杨氏弹性模量数据处理,处理杨氏弹性模量的工具,一个小程序
用弯曲法测杨氏模量实验报告(无数据版) 大学物理实验报告
#资源达人分享计划#
基于声卡和Matlab的数据采集系统在杨氏模量测量中的应用.pdf
静态拉伸法测定金属丝杨氏模量实验的最佳条件与数据处理
#资源达人分享计划#
10杨氏之子课件.ppt
CSDN海神之光上传的全部代码均可运行,亲测可用,尽我所能,为你服务; 1、代码压缩包内容 主函数:copper_wire_example.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若...
#资源达人分享计划#
基于MATLAB的最小二乘法处理杨氏模量测量数据的研究