本文共 2295 字，大约阅读时间需要 7 分钟。
搜索2维数组；如果数组中存在目标值，返回true，否则返回false
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
For example,
Consider the following matrix:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
Given target = 5, return true.
Given target = 20, return false.
遍历的话肯定效率低下。设立游标移动搜索。那么问题是从哪里开始搜索？
比较好的办法是从右上角开始。如果右上角的数字大于target，那么这一列没有target；向左一列移动
如果小于target，那么这一行没有target，向下一行移动
搜索停止的条件就是越界
Java代码：
1 package com.rust.cal; 2 3 public class Searcha2DMatrixII { 4 5 public static boolean searchMatrix(int[][] matrix, int target) { 6 if (matrix.length == 0 || matrix[0].length == 0) { 7 return false; 8 } 9 int dy = matrix[0].length - 1;10 int delta = matrix[0][dy];11 int dx = 0;12 while(dx < matrix.length && dy >= 0){13 if (matrix[dx][dy] == target) {14 return true;15 } else if (matrix[dx][dy] < target) {16 dx++;17 } else {18 dy--;19 }20 }21 return false;22 }23 public static void main(String args[]){24 int matrix[][] = {25 {1 ,2 ,3 ,4 ,9 },26 {6 ,7 ,8 ,10,19},27 {17,18,30,31,32}28 };29 30 int matrix1[][] = {31 {1,2},32 {4,5},33 {6,17},34 {10,20}35 };36 37 int matrix2[][] = {38 {1,3,5,7,9,13,17},39 {2,4,6,8,10,16,20}40 };41 42 System.out.println("matrix has 17? " + searchMatrix(matrix, 17));43 System.out.println("matrix has 18? " + searchMatrix(matrix, 18));44 System.out.println("matrix has 19? " + searchMatrix(matrix, 19));45 System.out.println("matrix1 has 4? " + searchMatrix(matrix1, 4));46 System.out.println("matrix2 has 4? " + searchMatrix(matrix2, 4));47 48 }49 } 输出：
matrix has 17? truematrix has 18? truematrix has 19? truematrix1 has 4? truematrix2 has 4? true
转载地址：http://ssvrx.baihongyu.com/