43 搜索二维矩阵

ops/2024/12/14 9:34:48/

43 搜索二维矩阵

在这里插入图片描述

43.1 搜索二维矩阵解决方案

解决思路

  • 将二维矩阵映射为一维数组的形式:
    • 如果矩阵有m行和n列,那么二维矩阵的下标(row,col)可以通过以下公式映射为一维下表index: i n d e x = r o w × n + c o l index = row × n +col index=row×n+col
    • 反之,如果有一维下表index,可以通过以下公式还原为二维下标(row,col): r o w = i n d e x / / n , c o l = i n d e x % n row = index // n,col = index \% n row=index//n,col=index%n
  • 使用二分查找:
    • 将左指针left初始化为0,右指针right初始化为矩阵元素总数减1.
    • 通过上述公式找到当前中间位置mid对应的二维矩阵元素,并与目标值进行比较。
    • 根据根据比较结果更新左右指针,直到目标值或搜索范围为空。
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if (matrix.empty() || matrix.[0].empty()){return false; // 边界条件,处理空矩阵}int m = matrix.size(); // 矩阵的行数int n = matrix[0].size(); // 矩阵的列数int left =0, right = m * n - 1; // 二分查找的范围while (left <= right){int mid = left + (right - left) / 2; // 防止溢出int midValue = matrix[mid / n][mid % n]; // 映射到二维矩阵if (midValue == target){return true;// 找到目标值} else if(midValue < target){left = mid + 1; // 缩小范围到右侧} else {right = mid - 1; // 缩小范围到左侧}}return false;// 没找到目标值}
};

43.2 举例说明

输入

matrix = {{1, 3, 5, 7},{10, 11, 16, 20},{23, 30, 34, 60}
};
target = 3;
  • 初始left = 0,right = 11(总共12个元素)。
  • 计算mid = 5,对应值为matrix[1][1] = 11,大于target,跟新right = 4.
  • 计算mid = 2,对应值为matrix[0][2] = 5,大于target,更新right = 1.
  • 计算mid = 1,对应值为martix[0][1] = 3,等于target,返回true.

http://www.ppmy.cn/ops/141777.html

相关文章

【LeetCode】每日一题 2024_12_13 K 次乘运算后的最终数组 I(暴力)

前言 每天和你一起刷 LeetCode 每日一题~ 小聊两句 1、今天是 12.13 南京大屠杀国家公祭日。铭记历史&#xff0c;勿忘国耻。 2、今天早上去看了 TGA 年度游戏颁奖&#xff0c;小机器人拿下了年度最佳游戏&#xff0c;所有人都震惊了&#xff0c;大伙纷纷问到&#xff0c;谁…

基于python实现自动化的验证码识别:探索与实践

基于python实现自动化的验证码识别&#xff1a;探索与实践 一、验证码的类型及特点&#xff08;一&#xff09;图像验证码&#xff08;二&#xff09;短信验证码&#xff08;三&#xff09;语音验证码 二、验证码识别的方法*&#xff08;一&#xff09;传统图像处理方法&#x…

红黑树(RBTree)

一、红黑树的概念 红黑树的每个节点都有颜色&#xff08;非黑即红&#xff09;&#xff0c;通过颜色来保证红黑树的平衡&#xff0c;是平衡搜索二叉树的一种。 二、红黑树的特性 1、任意一条路径上的节点都不能出现连续的红色节点。 2、最长路径不会超过最短路径的2倍。 3…

知识库系统,集成neo4j,集成activiti工作流,集成es全文检索,知识图谱血缘关系,nlp知识库

一、项目介绍 一款全源码&#xff0c;可二开&#xff0c;可基于云部署、私有部署的企业级知识库云平台&#xff0c;一款让企业知识变为实打实的数字财富的系统&#xff0c;应用在需要进行文档整理、分类、归集、检索、分析的场景。 为什么建立知识库平台&#xff1f; 助力企业…

DevExpress Blazor UI v24.1新版亮点:Scheduler(日程)组件全新升级

DevExpress Blazor UI组件使用了C#为Blazor Server和Blazor WebAssembly创建高影响力的用户体验&#xff0c;这个UI自建库提供了一套全面的原生Blazor UI组件&#xff08;包括Pivot Grid、调度程序、图表、数据编辑器和报表等&#xff09;。 DevExpress Blazor控件目前已经升级…

【含开题报告+文档+PPT+源码】基于微信小程序的点餐系统的设计与实现

开题报告 随着互联网技术的日益成熟和消费者生活水平与需求层次的显著提升&#xff0c;外卖点餐平台在中国市场上迅速兴起并深深植根于民众日常生活的各个角落。这类平台的核心在于构建了一个基于互联网的强大订餐服务系统&#xff0c;它无缝整合了餐饮商户资源与广大消费者的…

【新立电子】FPC材料的选择与性能优化

FPC柔性线路板&#xff0c;其材料的选择与性能优化&#xff0c;直接关系到电路板的整体性能、可靠性及应用范围&#xff0c;是电子工程师在设计和制造过程中必须高度重视的环节。 在材料选择上&#xff0c;FPC软性电路板倾向于采用高质量的基材、铜箔、覆盖膜及粘合剂。基材方…

在 Ubuntu 20.04 上安装和配置 Redis

在 Ubuntu 20.04 上安装和配置 Redis 文档概要 Redis 是一个开源的高性能键值数据库&#xff0c;广泛用于缓存、消息队列和实时分析等场景。本技术文档提供了在 Ubuntu 20.04 上安装、配置和测试 Redis 的完整步骤。 步骤 1&#xff1a;更新系统软件包列表 在安装 Redis 之前…