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;
    }
}
相关文章
|
5月前
|
数据采集 人工智能 安全
别再提“白帽GEO”了——为什么“合规GEO”才是对抗AI投毒的真正底线
本文批判滥用“白帽/黑帽”等过时SEO术语描述生成式引擎优化(GEO)乱象,指出AI投毒、虚假榜单等已逾越技术作弊范畴,触及法律与伦理红线。倡导以“合规GEO”取代理论失焦的旧话术,强调技术、平台、法律三层硬性底线——用对词,方能认清危险;守合规,才是真优化。(239字)
531 120
|
4月前
|
缓存 弹性计算 分布式计算
阿里云账号:计算型/通用型/内存型价格与场景区别
本文深度解析阿里云ECS三大主力实例:计算型(1:2)、通用型(1:4)、内存型(1:8)的硬件配比、适用场景与性价比逻辑。通过真实业务案例、价格测算与三步决策法,助企业告别“乱选配置”,精准匹配CPU与内存需求,避免资源浪费,实现降本增效。
|
4月前
|
运维
助力企业高效出海:阿里云国际站一站式上云与生态服务指南
随着出海加速,企业面临海外云账号开户难、跨境充值对账繁、风控响应慢等痛点。阿里云国际站联合生态伙伴,提供合规开户、多币种代充、统一账单及专属运维的一站式服务,助力跨境电商、游戏、SaaS等企业降本增效、稳健出海
|
5月前
|
人工智能 安全 中间件
AI编程迭代实测:SOLO与Composer vibe coding实战对比指南
TRAE SOLO是字节出品的AI原生IDE,专为中文vibe coding优化:初版代码即带中文注释、逻辑准确(CSDN评测准确率98%),JWT鉴权等需求1轮迭代即可落地;相较Cursor,bug更少、命名更规范、回退更稳,且基础版永久免费——真正适配国内开发者口述需求、快速迭代的后端开发场景。(239字)
|
8月前
|
安全 Linux 开发者
拒绝平庸:从零电平到操作系统,BootLoader硬核全景解析
本文深入解析BootLoader——嵌入式系统启动的“硅基唤醒者”。从硬件上电瞬间的CPU懵懂状态讲起,详述其初始化内存、搬运内核、设置异常向量、安抚看门狗、地址重定位等核心使命,并对比U-Boot、Barebox、LK等主流方案,展现其在驱动模型、网络启动、安全验证等高级特性上的强大能力。(239字)
1078 1
|
8月前
|
机器学习/深度学习 人工智能 自然语言处理
tiktoken 对中文长文本的压缩率实证研究——基于百万 token 对话的三层量化框架验证
随着大模型长上下文能力的普及,tiktoken 及其他 BPE based 分词器已成为评估文本 token 数的标准工具。然而,其在中英文混合长文本中的实际压缩规律仍缺乏实证验证,业界普遍使用的经验公式(如中文字符 × 1.6)尚未在大规模语料上得到检验。本文基于 DeepSeek 百万 token项目中提纯后的对话数据(.jsonl,1 077 046 tokens,3 673 轮)采用反向推算方法,首次在真实中文长文本上量化了tiktoken 的压缩系数。主要发现: 1️⃣ 中文实际系数约为 1.16,远低于经验公式的 1.6,导致整体 token 估算高出20.9 %; 2️⃣ 对话呈
|
11月前
|
消息中间件 分布式计算 Kafka
别再全量拉表了兄弟:一篇讲透增量数据处理与 CDC 的实战指南
别再全量拉表了兄弟:一篇讲透增量数据处理与 CDC 的实战指南
485 9
|
10月前
|
数据可视化 数据挖掘 测试技术
用户需求与反馈管理工具:构建产品持续进化的循环系统
本文系统阐述用户需求管理的完整框架,涵盖需求的四个层次、冰山法则及三维度评估体系,提出四步闭环方法论,并针对不同需求类型提供处理策略与工具推荐,助力团队从被动收集转向主动洞察,实现产品与用户的深度共鸣。
|
机器学习/深度学习 人工智能 编解码
AI-Compass LLM合集-多模态模块:30+前沿大模型技术生态,涵盖GPT-4V、Gemini Vision等国际领先与通义千问VL等国产优秀模型
AI-Compass LLM合集-多模态模块:30+前沿大模型技术生态,涵盖GPT-4V、Gemini Vision等国际领先与通义千问VL等国产优秀模型
AI-Compass LLM合集-多模态模块:30+前沿大模型技术生态,涵盖GPT-4V、Gemini Vision等国际领先与通义千问VL等国产优秀模型
|
存储 JSON NoSQL
JSON 存入 Redis
【7月更文挑战第8天】
757 12