每天一道leetcode-74 在二维数组中搜索n

乔戈里

发布于 2019-09-17 14:58:33

8450

发布于 2019-09-17 14:58:33

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

前言

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

题目

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

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

英文链接：

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

中文链接：

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

题目详述

编写一个高效的算法来判断 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

题目详解

第一种方法

思路

这道题多数人看到这道题的时候，肯定就是想到剑指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行就是思路中第二步的体现。

第二种方法

思路

前面已经说了，这道题的分类是属于二分查找的这一类，所以肯定可以使用二分查找这个方法去解决，关键是如何转换为二分查找。
二分查找的话关键是要找到中间的值，大于这个中间值，就是往右半边去找，小于这个中间值，就是往左半边去找，这里我结合我的代码进行讲解好一些。

代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0)
            return false;
        int n = matrix[0].length;
        int left = 0;
        int right = matrix.length*matrix[0].length - 1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(target == matrix[mid/n][mid%n])
                return true;
            else if(target < matrix[mid/n][mid%n])
                right = mid - 1;
            else
                left = mid + 1;
        }
        return false;
    }
}

我举一个例子方便大家理解。

示例 1:

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

在这个示例中，1,3,5,7是第一行，10,11,16,20是第二行，23,30,34,50是第三行。总共有3*4=12个数，按照从0开始的方式，所以left=0,right=12-1=11,也就是代码6-7行所示；
mid是二者去中间值，没毛病，mid=5第10行所示；
难点就在于matrix[mid/n][mid%n]的理解，就是对于一个下标如何确定它在二维数组中的位置，对于二维数组中，1来说，1是第0个数，第0/4行，3是第一个数，第0/4行，5是第2个数，第0/4行，7是第3个数，第0/4行，10是第4个数，第4/4行，11是5个数，第5/4行........观察规律可知，行数就是用它的下标值去除以列的长度（matrix[0].length）也就是4；
同理对于列来说，1是第0个数，第0%4=0列，3是第1个数，第1%4=1列，5是第2个数，第2%4=2列，7是第3个数，第3%4列，10是第4个数，第4%4=0列.......观察规律可知，列数就是用它的下标值去对于4（matrix[0].length）取余。
所以mid的下标对应的二维数组中的数就是matrix[mid/4][mid%4];

结果展示