LeetCode74 搜索二维矩阵 2019.5.26

题目：

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

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

示例 1:

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

示例 2:

输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false

方法一：直接暴力

class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix.length==0 || matrix[0].length == 0){ return false; } int m = matrix.length; int n = matrix[0].length; int local = -1; for (int i = 0; i < m; i++){ int min = matrix[i][0]; int max = matrix[i][n - 1]; if (target == min || target == max){ return true; } if (target > min && target < max){ local = i; break; } } if (local == -1) return false; for (int i = 0; i < n; i++){ if (matrix[local][i] == target){ return true; } } return false; }

方法二：

从右上角看，可将矩阵看成一个二叉搜索树

public class SolutionOptimize { public boolean searchMatrix(int[][] matrix, int target) { if (matrix.length == 0 || matrix[0].length == 0){ return false; } int m = matrix.length; int n = matrix[0].length; int i = 0, j = n - 1; // 从右上角开始寻找target while(i >= 0 && i < m && j >= 0 && j < n){ if (matrix[i][j] == target){ return true; } else if (matrix[i][j] > target){ j--; } else if (matrix[i][j] < target){ i++; } } return false; } }