甲骨文Java培训—杨氏矩阵查找元素位置Java实现

甲骨文Java—杨氏矩阵查找元素位置Java实现 甲骨文Java培训—杨氏矩阵查找元素位置Java实现 杨氏矩阵是一个二维矩阵，特点是每一行的右边的元素比左边的大，每一列下面的元素比上面的大; 比如 1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15 假设要查找的变量为target，我刚开始的想法是先定位到target的纵坐标;先找到target可能所在的行，然后再在那行遍历横坐标;这种方法是最暴力的方法，而且所需的时间复杂度是O(m*n)显然不是一个好的做法; 考虑到杨氏矩阵的特性;先给一个比较的基准点;例如 第4行第4列的元素5，如果要查找的target比基准点大，那么是在基准点元素的右方或者下方;如果查找的点比基准点小，那么元素可能在元素的左方或者上方;这样就会出现元素重叠出现在两个区域的情况; 再仔细想想，有没有更好的方法实现呢? 可以考虑以右上角的节点为基准点，如果查找的元素比基准点小，那么基准点所在的列就可以排除了;如果查找的元素比基准点大，那么基准点所在的行就可以排除了，就这样反复排除，最后可以把时间复杂度降低到O(m+n)，从左下角开始查找也是同样的道理，但是左上角和右下角就不行了，无法做到剔除某列或某行的效果; 基于这种思想;用Java做了如下的实现; 此题可以分为几种求法，可能是求是否能找到点，目标节点的坐标?所有目标节点的坐标?我实现了所有节点的坐标; 哇，写完了还挺多，想的比较多，矩阵还得判断各种合法性，反正多考虑一些总是对的嘛，我这简单就打印一下，具体可能会记日志神码的 package design; import java.util.ArrayList; import java.util.List; public class YoungTableau { private int row; private int column; private int value; public YoungTableau(int x, int y, int value) { super(); this.setRow(x); this.setColumn(y); this.setValue(value); } public YoungTableau() { } /** * @param args */ public static void main(String args[]) { int matrix[][] = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } }; /** * 测试用例 1 input error matrix,column,row 2 test target>all elements or * target< between target test 3 elements> */ printMatrix(matrix, 4, 4); find(matrix, 4, 4, -3); find(null, 4, 4, 88); find(matrix, 0, 4, 5); find(matrix, 4, -2, 5); find(matrix, 4, 4, 5); find(matrix, 4, 4, 7); find(matrix, 4, 4, 1000); find(matrix, 4, 4, -1); } /** * @param matrix * @param rows * @param columns * @return 判断矩阵输入合法性 */ private static boolean isValid(int[][] matrix, int rows, int columns) { boolean isValid = false; /** 判断二维矩阵每列合法性 */ if (matrix != null && rows > 0 && columns > 0) { int rowLength = matrix.length; if (columns <= rowLength) { int columnLength = matrix[0].length; for (int i = 1; i < rowLength; i++) { columnLength = columnLength > matrix[i].length ? columnLength : matrix[i].length; if (columnLength > columns) { return isValid; } } isValid = true; } } else { System.out.println("矩阵输入非法"); } return isValid; } /** * @param result */ public static void printResult(List result) { System.out.println("=====Begin====="); if (result.size() == 0) { System.out.println("There is no result"); } for (YoungTableau yt : result) { System.out.println("find value:" + yt.getValue() + " column:" + yt.getRow() + " column:" + yt.getColumn()); } System.out.println("=====End====="); } /** * @param matrix * @param rows * @param columns * @param target * @return */ public static List find(int[][] matrix, int rows, int columns, int target) { List result = new ArrayList(); /** 判空及异常的判断 */ if (isValid(matrix, rows, columns)) { /** 先以右上角的节点为开始 */ int row = 0; int column = columns - 1; /** 结束循环的条件 */ while (row < rows && column >= 0) { if (target == matrix[row][column]) { /** 节点找到，向result加入节点元素 */ result.add(new YoungTableau(row, column, matrix[row][column])); /** 如果找到，那么这行和这列都可以去掉 */ column--; row++; } else if (target < matrix[row][column]) { /** 节点比基准点小，target所在列可以去除 */ column--; } else { /** 节点比基准点大，target所在行可以去除 */ row++; } } } /** 这里为了方便直接打印一下 */ printResult(result); return result; } /** * @param source * @param rows * @param columns * 打印矩阵，调用的方法已经判空，此处省略 */ public static void printMatrix(int[][] matrix, int rows, int columns) { if (isValid(matrix, rows, columns)) { for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { System.out.print(matrix[i][j] + "\t"); } System.out.println(); } } } public void setRow(int row) { this.row = row; } public int getRow() { return row; } public void setColumn(int column) { this.column = column; } public int getColumn() { return column; } public void setValue(int value) { this.value = value; } public int getValue() { return value; } } 盈佳科技有限公司是甲骨文Oracle公司在北京指定授权IT学习中心，坐落于海淀区北四环中路。主要从事OracleJava软件开发实训和学员的就业安排。Oracle Java软件开发实训课程摆脱了传统单一编程训练的知识结构，整个实训体系分为技术层面、理论层面、软件项目管理层面及团队合作层面。学员不仅能够学习到实用的技术，更可以在多方面得到综合训练，从而培养出适合企业需要的高素质人才。详情请访问:甲骨文官网网址: