楊氏矩陣查找元素位置Java實現

　　楊氏矩陣是一個二維矩陣特點是每一行的右邊的元素比左邊的大每一列下面的元素比上面的大;

　　比如

　　

　　

　　

　　

　　假設要查找的變量為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;

　　}

　　}

From:http://tw.wingwit.com/Article/program/Java/hx/201311/25731.html