Go语言视频零基础入门到精通

javalearner

杨氏矩阵是一个二维矩阵，特点是每一行的右边的元素比左边的大，每一列下面的元素比上面的大; 比如:
  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做了如下的实现; 此题可以分为几种求法，可能是求是否能找到点，目标节点的坐标?所有目标节点的坐标?我实现了所有节点的坐标;   哇，写完了还挺多，想的比较多，矩阵还得判断各种合法性，反正多考虑一些总是对的嘛，我这简单就打印一下，具体可能会记日志神码的。

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

复制代码

运行结果：
C:java>java YoungTableau
=====Begin=====
There is no result
=====End=====
=====Begin=====
There is no result
=====End=====
=====Begin=====
find value:4 column:1 column:1
find value:4 column:2 column:0
=====End=====



  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/15/000001640.zip