每天一道leetcode240-在二维数组中搜索n升级版

乔戈里

发布于 2019-09-17 15:03:26

6940

发布于 2019-09-17 15:03:26

文章被收录于专栏：Java那些事

前言

这道题目只需要一些简单的java语法知识，就可以看懂。

题目

leetcode-240 在二维数组中搜索一个数Ⅱ

分类(tag):二分查找这一类

英文链接：

https://leetcode.com/problems/search-a-2d-matrix-ii/

中文链接：

https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

题目详述

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

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

示例:

现有矩阵 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。

给定 target = 20，返回 false。

昨天的题目：每天一道leetcode-74 在二维数组中搜索n

这道题和昨天的那道题不同地方是昨天的那道题每行的·最末尾的数字必然小于下一行的开头的数字，今天这个题目每行的·最末尾的数字与下一行的开头的数字没有必然的联系

题目详解

第一种方法

思路

这道题多数人看到这道题的时候，肯定就是想到剑指offer的思路.就是比较矩阵的右上角的数与target的大小，如果target比这个矩阵右上角的数大，由于矩阵的右上角元素A是A所在行的最大的值，所以target肯定不在A所在的行了，所以这时候就应该就在除去第一行的剩下的行中去找这个target;
如果target比矩阵右上角的数A小，那么由于A所在的列中A是最小的，那么target就在除去最右边的列的其它的列；
如果相等，返回true;

代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0)
            return false;
        int rowIndex = 0;//代表下标 
        int colIndex = matrix[0].length - 1;//代表下标
        while(rowIndex < matrix.length && colIndex  >=0)
        {
            if(target == matrix[rowIndex][colIndex])
                return true;
            else if(target > matrix[rowIndex][colIndex])
                rowIndex++;
            else
                colIndex--;
        }
        return false;
    }
}

代码11到12行就是思路中第一步的体现，13-14行就是思路中第二步的体现。

第二种方法

思路

前面已经说了，这道题的分类是属于二分查找的这一类，所以肯定可以使用二分查找这个方法去解决，关键是如何转换为二分查找。
二分查找的话关键是要找到中间的值，由于这道题目是数字并不是依次递增的，所以无法利用昨天的那道题目的思路来解决；昨天的题目：每天一道leetcode-74 在二维数组中搜索n
感觉微信名为NLogN的群友提供的思路，他看了我昨天的那道题目，然后和我说着到题目先按照第一列进行二分，这样确定了target可能在哪几行，然后他后续的的思路我对其进行了这样的改进，上面已经确定了在哪几行，然后再每一行中相当于一个数组找一个数target，继续二分查找；遍历完每一行，最后就可以确定target到底在不在。

代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0 || matrix[0].length == 0)
            return false;
        int begin = 0;
        int end = matrix.length - 1;
        int midRow = (begin + end) / 2;
        while(begin <= end)
        {
            midRow = begin + (end - begin) / 2;
            if(target == matrix[midRow][0])
                return true;
            else if(target > matrix[midRow][0])
                begin = midRow + 1;
            else
                end = midRow - 1;
        }
        for(int i=0;i<=midRow;i++)
        {
            int left = 0;
            int right = matrix[0].length-1;
            while(left <= right)
            {
                int mid = left + (right-left)/2;
                if(matrix[i][mid] == target)
                    return true;
                else if(matrix[i][mid] < target)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return false;
    }
}