杨氏矩阵是一个二维矩阵特点是每一行的右边的元素比左边的大每一列下面的元素比上面的大;
比如
假设要查找的变量为target我刚开始的想法是先定位到target的纵坐标;先找到target可能所在的行然后再在那行遍历横坐标;这种方法是最暴力的方法而且所需的时间复杂度是O(m*n)显然不是一个好的做法;
考虑到杨氏矩阵的特性;先给一个比较的基准点;例如 第行第列的元素如果要查找的target比基准点大那么是在基准点元素的右方或者下方;如果查找的点比基准点小那么元素可能在元素的左方或者上方;这样就会出现元素重叠出现在两个区域的情况;
再仔细想想有没有更好的方法实现呢?
可以考虑以右上角的节点为基准点如果查找的元素比基准点小那么基准点所在的列就可以排除了;如果查找的元素比基准点大那么基准点所在的行就可以排除了就这样反复排除最后可以把时间复杂度降低到O(m+n)从左下角开始查找也是同样的道理但是左上角和右下角就不行了无法做到剔除某列或某行的效果;
基于这种思想;用Java做了如下的实现;
此题可以分为几种求法可能是求是否能找到点目标节点的坐标?所有目标节点的坐标?我实现了所有节点的坐标;
哇写完了还挺多想的比较多矩阵还得判断各种合法性反正多考虑一些总是对的嘛我这简单就打印一下具体可能会记日志神码的
package design;
import javautilArrayList;
import javautilList;
public class YoungTableau {
private int row;
private int column;
private int value;
public YoungTableau(int x int y int value) {
super();
thissetRow(x);
thissetColumn(y);
thissetValue(value);
}
public YoungTableau() {
}
/**
* @param args
*/
public static void main(String args[]) {
int matrix[][] = { { } { } { }
{ } };
/**
* 测试用例 input error matrixcolumnrow test target>all elements or
* target
*/
printMatrix(matrix );
find(matrix );
find(null );
find(matrix );
find(matrix );
find(matrix );
find(matrix );
find(matrix );
find(matrix );
}
/**
* @param matrix
* @param rows
* @param columns
* @return 判断矩阵输入合法性
*/
private static boolean isValid(int[][] matrix int rows int columns) {
boolean isValid = false;
/** 判断二维矩阵每列合法性 */
if (matrix != null && rows > && columns > ) {
int rowLength = matrixlength;
if (columns <= rowLength) {
int columnLength = matrix[]length;
for (int i = ; i < rowLength; i++) {
columnLength = columnLength > matrix[i]length ? columnLength
: matrix[i]length;
if (columnLength > columns) {
return isValid;
}
}
isValid = true;
}
} else {
Systemoutprintln(矩阵输入非法);
}
return isValid;
}
/**
* @param result
*/
public static void printResult(List result) {
Systemoutprintln(=====Begin=====);
if (resultsize() == ) {
Systemoutprintln(There is no result);
}
for (YoungTableau yt : result) {
Systemoutprintln(find value: + ytgetValue() + column:
+ ytgetRow() + column: + ytgetColumn());
}
Systemoutprintln(=====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 = ;
int column = columns ;
/** 结束循环的条件 */
while (row < rows && column >= ) {
if (target == matrix[row][column]) {
/** 节点找到向result加入节点元素 */
resultadd(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 = ; i < rows; i++) {
for (int j = ; j < columns; j++) {
Systemoutprint(matrix[i][j] + \t);
}
Systemoutprintln();
}
}
}
public void setRow(int row) {
thisrow = row;
}
public int getRow() {
return row;
}
public void setColumn(int column) {
lumn = column;
}
public int getColumn() {
return column;
}
public void setValue(int value) {
thisvalue = value;
}
public int getValue() {
return value;
}
}
