LeetCode 74. Search a 2D Matrix题目分析代码

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example, Consider the following matrix: [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] Given target = 3, return true.

题目

写出一个高效的算法来搜索 m × n矩阵中的值。 这个矩阵具有以下特性:

  • 每行中的整数从左到右是排序的。
  • 每行的第一个数大于上一行的最后一个整数。 样例 考虑下列矩阵:
[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

给出 target = 3,返回 true

分析

本题主要考察的是二分法,但是这里如何使用二分法又有不同的策略,但本质都是一样的 方法一,我们二分,先从每列的最后一个数开始,确定它的列再搜索行 方法二,就是将二维数组展开一维数组,然后二分法中间的数 方法三,就是分别求行和列,求行时,用二分法,然后求列在用二分法。

代码

方法一

public class Solution {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here
        if(matrix == null)
            return false;
        int rows=matrix.length;
        if(rows == 0 )
            return false;
        // 行数     
        int cols=matrix[0].length;  // 列数        
        int i=0, j=cols-1;    
        boolean found = false;    
        while(j>=0 && j<cols && i<rows)   //  i>=0 默认满足,无须再判断     
        {    
            if(matrix[i][j] == target) { found = true;  break; }                   
            else if(matrix[i][j] > target) j--;  // 如果矩阵右上角的值比target大,删除所在的列,列号-1     
            else i++;                           // 如果矩阵右上角的值不大于target,删除所在的行,行号+1    
        }                 
        return found;
        
    }
}

方法二

public class Solution {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
        
        int row = matrix.length, column = matrix[0].length;
        int start = 0, end = row * column - 1;
        
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int number = matrix[mid / column][mid % column];
            if (number == target) {
                return true;
            } else if (number < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (matrix[start / column][start % column] == target) {
            return true;
        } else if (matrix[end / column][end % column] == target) {
            return true;
        }
        
        return false;
    }
}

方法三

public class Solution {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
        
        int row = matrix.length;
        int column = matrix[0].length;
        
        // find the row index, the last number <= target 
        int start = 0, end = row - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid][0] == target) {
                return true;
            } else if (matrix[mid][0] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (matrix[end][0] <= target) {
            row = end;
        } else if (matrix[start][0] <= target) {
            row = start;
        } else {
            return false;
        }
        
        // find the column index, the number equal to target
        start = 0;
        end = column - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (matrix[row][start] == target) {
            return true;
        } else if (matrix[row][end] == target) {
            return true;
        }
        return false;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

Spark MLlib 之 Vector向量深入浅出

local vector是一种索引是0开始的整数、内容为double类型,存储在单机上的向量。MLlib支持两种矩阵,dense密集型和sparse稀疏型。一个...

39500
来自专栏繁花云

[C语言]7-3笔记

对数的定义:一般地,如果ax=N(a>0,且a≠1),那么数x叫做以a为底N的对数,记作x=logaN,读作以a为底N的对数,其中a叫做对数的底数,N叫做真数。

9800
来自专栏mathor

子数组累加和为aim(小于等于aim)的三个问题

 这个和上面唯一的不同就是数组中只有正数,这里使用类似窗口移动的做法,给出两个指针,L,R表示窗口的左右边界 ,sum表示的是arr[L,R]之间的累加和,L,...

13720
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程2

教程 OpenGLES入门教程1-Tutorial01-GLKit 这次的是shader编译链接、glsl入门和简单图形变换。 OpenGL ES系列教程在这...

33380
来自专栏架构之路

并查集Union-find及其在最小生成树中的应用

并查集是一种用途广泛的数据结构,能够快速地处理集合的合并和查询问题,并且实现起来非常方便,在很多场合中都有着非常巧妙的应用,。 本文首先介绍并查集的定义、原理及...

40640
来自专栏鸡蛋君

计算机等级考试二级MsOffice之Excel函数学习

12230
来自专栏ml

机器学习之KNN算法思想及其实现

从一个例子来直观感受KNN思想 如下图 , 绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色...

438130
来自专栏王肖的UT

GLSL-内置函数

75330
来自专栏desperate633

LeetCode 149. Max Points on a Line分析代码

将x,y的差值求最大公约数,约到最简洁的形式,然后存入map中,对每个点这样操作,如果最后x,y最后相等,那么就说明两个点具有相同的斜率,在一条直线上。同时不要...

11730
来自专栏Java帮帮-微信公众号-技术文章全总结

Java案例-分数查等级程序

Java案例-分数查等级程序 给定一个百分制的分数,输出相应的等级。 90分以上 A级 80~89 B级 70~79 C级 ...

41680

扫码关注云+社区

领取腾讯云代金券