搜索二维矩阵

[toc]

题目描述

编写一个高效的算法来判断mxn矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

思路

从右上角的值current开始判断，有3种情况

• case0: current=target 直接return true
• case1: current>target 表示target在当前行，column-1，继续用右上角的值判断
• case2: current<target 表示target在下面行，row+1，继续用右上角判断

如此 直到row>length-1或者column<0,return false

代码实现

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 从右上角的值current开始判断，有两种情况
        //     case0: current=target  直接return true
        //     case1: current>target  表示target在当前行，column-1，继续用右上角的值判断
        //     case2: current<target  表示target在下面行，row+1，继续用右上角判断
        // 如此 直到row>length-1或者column<0,return false
        int row = 0;
        int column = matrix[0].length-1;
        while(row<matrix.length && column>=0){
            if(matrix[row][column] == target) return true;
            else if(matrix[row][column] > target) column--;
            else if(matrix[row][column] < target) row++;
        }
        return false;
    }
}