大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 杨氏矩阵查找元素位置Java实现

杨氏矩阵查找元素位置Java实现

关键词:杨氏矩阵杨氏矩阵查找元素位置Java实现  阅读(621) 赞(13)

[摘要]本文主要是对杨氏矩阵查找元素位置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

  */

  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;

  }

  }



相关评论