杨氏矩阵查找元素位置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做了如下的实现;

此题可以分为几种求法,可能是求是否能找到点,目标节点的坐标?所有目标节点的坐标?我实现了所有节点的坐标;

哇,写完了还挺多,想的比较多,矩阵还得判断各种合法性,反正多考虑一些总是对的嘛,我这简单就打印一下,具体可能会记日志神码的

 

[java][/java] view plaincopy

  1. package design;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. public class YoungTableau {
  5.     private int row;
  6.     private int column;
  7.     private int value;
  8.     public YoungTableau(int x, int y, int value) {
  9.         super();
  10.         this.setRow(x);
  11.         this.setColumn(y);
  12.         this.setValue(value);
  13.     }
  14.     public YoungTableau() {
  15.     }
  16.     /**
  17.      * @param args
  18.      */
  19.     public static void main(String args[]) {
  20.         int matrix[][] = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 },
  21.                 { 6, 8, 11, 15 } };
  22.         /**
  23.          * 测试用例 1 input error matrix,column,row 2 test target>all elements or
  24.          * target<all elements 3 test target between elements
  25.          */
  26.         printMatrix(matrix, 4, 4);
  27.         find(matrix, 4, 4, -3);
  28.         find(null, 4, 4, 88);
  29.         find(matrix, 0, 4, 5);
  30.         find(matrix, 4, -2, 5);
  31.         find(matrix, 4, 4, 5);
  32.         find(matrix, 4, 4, 7);
  33.         find(matrix, 4, 4, 1000);
  34.         find(matrix, 4, 4, -1);
  35.     }
  36.     /**
  37.      * @param matrix
  38.      * @param rows
  39.      * @param columns
  40.      * @return 判断矩阵输入合法性
  41.      */
  42.     private static boolean isValid(int[][] matrix, int rows, int columns) {
  43.         boolean isValid = false;
  44.         /** 判断二维矩阵每列合法性 */
  45.         if (matrix != null && rows > 0 && columns > 0) {
  46.             int rowLength = matrix.length;
  47.             if (columns <= rowLength) {
  48.                 int columnLength = matrix[0].length;
  49.                 for (int i = 1; i < rowLength; i++) {
  50.                     columnLength = columnLength > matrix[i].length ? columnLength
  51.                             : matrix[i].length;
  52.                     if (columnLength > columns) {
  53.                         return isValid;
  54.                     }
  55.                 }
  56.                 isValid = true;
  57.             }
  58.         } else {
  59.             System.out.println(“矩阵输入非法”);
  60.         }
  61.         return isValid;
  62.     }
  63.     /**
  64.      * @param result
  65.      */
  66.     public static void printResult(List<YoungTableau> result) {
  67.         System.out.println(“=====Begin=====”);
  68.         if (result.size() == 0) {
  69.             System.out.println(“There is no result”);
  70.         }
  71.         for (YoungTableau yt : result) {
  72.             System.out.println(“find value:” + yt.getValue() + ” column:”
  73.                     + yt.getRow() + ” column:” + yt.getColumn());
  74.         }
  75.         System.out.println(“=====End=====”);
  76.     }
  77.     /**
  78.      * @param matrix
  79.      * @param rows
  80.      * @param columns
  81.      * @param target
  82.      * @return
  83.      */
  84.     public static List<YoungTableau> find(int[][] matrix, int rows,
  85.             int columns, int target) {
  86.         List<YoungTableau> result = new ArrayList<YoungTableau>();
  87.         /** 判空及异常的判断 */
  88.         if (isValid(matrix, rows, columns)) {
  89.             /** 先以右上角的节点为开始 */
  90.             int row = 0;
  91.             int column = columns – 1;
  92.             /** 结束循环的条件 */
  93.             while (row < rows && column >= 0) {
  94.                 if (target == matrix[row][column]) {
  95.                     /** 节点找到,向result加入节点元素 */
  96.                     result.add(new YoungTableau(row, column,
  97.                             matrix[row][column]));
  98.                     /** 如果找到,那么这行和这列都可以去掉 */
  99.                     column–;
  100.                     row++;
  101.                 } else if (target < matrix[row][column]) {
  102.                     /** 节点比基准点小,target所在列可以去除 */
  103.                     column–;
  104.                 } else {
  105.                     /** 节点比基准点大,target所在行可以去除 */
  106.                     row++;
  107.                 }
  108.             }
  109.         }
  110.         /** 这里为了方便直接打印一下 */
  111.         printResult(result);
  112.         return result;
  113.     }
  114.     /**
  115.      * @param source
  116.      * @param rows
  117.      * @param columns
  118.      *            打印矩阵,调用的方法已经判空,此处省略
  119.      */
  120.     public static void printMatrix(int[][] matrix, int rows, int columns) {
  121.         if (isValid(matrix, rows, columns)) {
  122.             for (int i = 0; i < rows; i++) {
  123.                 for (int j = 0; j < columns; j++) {
  124.                     System.out.print(matrix[i][j] + “\t”);
  125.                 }
  126.                 System.out.println();
  127.             }
  128.         }
  129.     }
  130.     public void setRow(int row) {
  131.         this.row = row;
  132.     }
  133.     public int getRow() {
  134.         return row;
  135.     }
  136.     public void setColumn(int column) {
  137.         this.column = column;
  138.     }
  139.     public int getColumn() {
  140.         return column;
  141.     }
  142.     public void setValue(int value) {
  143.         this.value = value;
  144.     }
  145.     public int getValue() {
  146.         return value;
  147.     }
  148. }

标签