Leetcode Hot 100刷题记录 -Day17（搜索二维矩阵II）

搜索二维矩阵II

问题描述：

        编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：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]], target = 5
输出：true

示例 2：

输入：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]], target = 20
输出：false

解题思路：

采用二分查找！！！

• 矩阵不存在，返回false
• 某一行的第一个元素大于了 target ，当前行和后边的所有行都不用考虑了，直接返回 false
• 某一行的最后一个元素小于了 target ，当前行就不用考虑了，换下一行

//提交版

class Solution {
     public boolean searchMatrix(int[][] matrix, int target){
        if(matrix.length==0 || matrix[0].length == 0)
            return false;
        for (int i =0;i<matrix.length;i++){
            if (matrix[i][0] > target)
                return false;
            if ((matrix[i][matrix[i].length - 1]) < target)
                continue;
            int col = binarySearch(matrix[i], target);
            if (col != -1)
                return true;
        }
        return false;
    }

    public int binarySearch(int[] nums, int target){
        int low = 0;
        int high = nums.length-1;
        while (low <= high){
            int mid = (high - low)/2 + low;
            int num = nums[mid];
            if (num == target)
                return mid;
            else if (num > target) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        return -1;
    }
}


//带有输入输出版
import java.util.Arrays;

public class hot18_searchMatrix {
    public boolean searchMatrix(int[][] matrix, int target){
        if(matrix.length==0 || matrix[0].length == 0)
            return false;
        for (int i =0;i<matrix.length;i++){
            if (matrix[i][0] > target)
                return false;
            if ((matrix[i][matrix[i].length - 1]) < target)
                continue;
            int col = binarySearch(matrix[i], target);
            if (col != -1)
                return true;
        }
        return false;
    }

    public int binarySearch(int[] nums, int target){
        int low = 0;
        int high = nums.length-1;
        while (low <= high){
            int mid = (high - low)/2 + low;
            int num = nums[mid];
            if (num == target)
                return mid;
            else if (num > target) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args){
        int[][] 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}};
        int target = 5;
        System.out.println("输入：" + Arrays.deepToString(matrix));
        hot18_searchMatrix hot18SearchMatrix = new hot18_searchMatrix();
        boolean result = hot18SearchMatrix.searchMatrix(matrix,target);
        System.out.println("输出：" + result);
    }

}