74_搜索二维矩阵

简介: 74_搜索二维矩阵

74、搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵:

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false

示例 1:

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

示例 2:

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

【思路】

由于每行的第一个元素大于前一行的最后一个元素,且每行元素是升序的,所以每行的第一个元素大于前一行的第一个元素,因此矩阵第一列的元素是升序的。可以对矩阵的第一列的元素二分查找,找到最后一个不大于目标值的元素,然后在该元素所在行中二分查找目标值是否存在。

//非二分查找法
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        for (i = matrix.length - 1; i > 0 ; i--) {
            if (matrix[i][0] <= target) {
                break;
            }
        }
        for (int j = 0; j < matrix[i].length; j++) {
            if (matrix[i][j] == target) 
                return true;
        }
        return false;
    }
}

//改为二分查找的方式来做

class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
    int rowIndex = binarySearchFirstColumn(matrix, target);
    if (rowIndex < 0) {
      return false;
    }
    return binarySearchRow(matrix[rowIndex], target);
  }
    public int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
    
    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            //用原来的也可以
            //int mid = (high + low) / 2;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}
相关文章
|
弹性计算 安全 数据安全/隐私保护
一、基于Fortinet的出海业务访问加速方案--详细部署步骤
本方案基于CADT提供一个一键交付零配置的部署模板,帮助企业快速构建出海业务访问加速的环境。方案结合了Fortinet产品以及阿里云的ECS,BGP公网精品IP等产品,实现低成本的出海业务加速。
598 0
|
区块链 数据安全/隐私保护
北京大学肖臻老师《区块链技术与应用》公开课笔记10——比特币分叉
北京大学肖臻老师《区块链技术与应用》公开课笔记10——比特币分叉
716 0
|
新零售 大数据
新零售,新在哪里?良品铺子携手阿里云打造数字样板间 | 云栖数字样板间
长于武汉,数字升级——良品铺子和阿里云的新零售之道 。
661 0
新零售,新在哪里?良品铺子携手阿里云打造数字样板间 | 云栖数字样板间
|
10天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
9天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
404 130
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
|
3天前
|
存储 安全 前端开发
如何将加密和解密函数应用到实际项目中?
如何将加密和解密函数应用到实际项目中?
197 138
|
9天前
|
人工智能 Java API
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)
本文介绍AI大模型的核心概念、分类及开发者学习路径,重点讲解如何选择与接入大模型。项目基于Spring Boot,使用阿里云灵积模型(Qwen-Plus),对比SDK、HTTP、Spring AI和LangChain4j四种接入方式,助力开发者高效构建AI应用。
377 122
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)