我的编程空间,编程开发者的网络收藏夹
学习永远不晚

C++如何实现搜索二维矩阵功能

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

C++如何实现搜索二维矩阵功能

本篇内容介绍了“C++如何实现搜索二维矩阵功能”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

[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.

Example 1:

C++如何实现搜索二维矩阵功能

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

Example 2:

C++如何实现搜索二维矩阵功能

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

Constraints:

  • m == matrix.length

  • n == matrix[i].length

  • 1 <= m, n <= 100

  • -104 <= matrix[i][j], target <= 104

这道题要求搜索一个二维矩阵,由于给的矩阵是有序的,所以很自然的想到要用二分查找法,可以在第一列上先用一次二分查找法找到目标值所在的行的位置,然后在该行上再用一次二分查找法来找是否存在目标值。对于第一个二分查找,由于第一列的数中可能没有 target 值,该如何查找呢,如果是查找第一个不小于目标值的数,当 target 在第一列时,会返回 target 所在的行,但若 target 不在的话,有可能会返回下一行,不好统一。所以可以查找第一个大于目标值的数,也就是总结帖中的第三类,这样只要回退一个,就一定是 target 所在的行。但需要注意的一点是,如果返回的是0,就不能回退了,以免越界,记得要判断一下。找到了 target 所在的行数,就可以再次使用二分搜索,此时就是总结帖中的第一类了,查找和 target 值相同的数,也是最简单的一类,分分钟搞定即可,参见代码如下:

解法一:

class Solution {public:    bool searchMatrix(vector<vector<int>>& matrix, int target) {        if (matrix.empty() || matrix[0].empty()) return false;        int left = 0, right = matrix.size();        while (left < right) {            int mid = (left + right) / 2;            if (matrix[mid][0] == target) return true;            if (matrix[mid][0] < target) left = mid + 1;            else right = mid;        }        int tmp = (right > 0) ? (right - 1) : right;        left = 0;        right = matrix[tmp].size();        while (left < right) {            int mid = (left + right) / 2;            if (matrix[tmp][mid] == target) return true;            if (matrix[tmp][mid] < target) left = mid + 1;            else right = mid;        }        return false;    }};

当然这道题也可以使用一次二分查找法,如果我们按S型遍历该二维数组,可以得到一个有序的一维数组,只需要用一次二分查找法,而关键就在于坐标的转换,如何把二维坐标和一维坐标转换是关键点,把一个长度为n的一维数组转化为 m*n 的二维数组 (m*n = n)后,那么原一维数组中下标为i的元素将出现在二维数组中的 [i/n][i%n] 的位置,有了这一点,代码很好写出来了:

解法二:

class Solution {public:    bool searchMatrix(vector<vector<int>>& matrix, int target) {        if (matrix.empty() || matrix[0].empty()) return false;        int m = matrix.size(), n = matrix[0].size();        int left = 0, right = m * n;        while (left < right) {            int mid = (left + right) / 2;            if (matrix[mid / n][mid % n] == target) return true;            if (matrix[mid / n][mid % n] < target) left = mid + 1;            else right = mid;        }        return false;    }};

这道题其实也可以不用二分搜索法,直接使用双指针也是可以的,i指向0,j指向列数,这样第一个被验证的数就是二维数组右上角的数字,假如这个数字等于 target,直接返回 true;若大于 target,说明要减小数字,则列数j自减1;若小于 target,说明要增加数字,行数i自增1。若 while 循环退出了还是没找到 target,直接返回 false 即可,参见代码如下:

解法三:

class Solution {public:    bool searchMatrix(vector<vector<int>>& matrix, int target) {        if (matrix.empty() || matrix[0].empty()) return false;        int i = 0, j = (int)matrix[0].size() - 1;        while (i < matrix.size() && j >= 0) {            if (matrix[i][j] == target) return true;            else if (matrix[i][j] > target) --j;            else ++i;        }           return false;    }};

“C++如何实现搜索二维矩阵功能”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站,小编将为大家输出更多高质量的实用文章!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

C++如何实现搜索二维矩阵功能

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

C++如何实现搜索二维矩阵功能

本篇内容介绍了“C++如何实现搜索二维矩阵功能”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成![LeetCode] 74. Search a
2023-06-20

javaweb搜索功能如何实现

要实现JavaWeb的搜索功能,可以按照以下步骤进行:1. 建立数据库:创建一个适合存储搜索内容的数据库表。例如,可以创建一个包含标题、内容和日期等字段的表。2. 创建搜索页面:创建一个搜索页面,包含一个搜索表单和一个展示搜索结果的区域。用
2023-09-21

vs中如何实现搜索功能

在VS中实现搜索功能可以通过以下步骤进行:1. 添加搜索框:在界面中添加一个文本框作为搜索框,供用户输入搜索关键字。2. 添加搜索按钮:在搜索框旁边添加一个按钮,用于触发搜索操作。3. 编写搜索功能的代码:在搜索按钮的点击事件中编写搜索功能
2023-08-23

vue如何实现搜索小功能

这篇文章主要介绍vue如何实现搜索小功能,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!具体内容如下
2023-06-21

C语言如何实现杨氏矩阵

本篇内容主要讲解“C语言如何实现杨氏矩阵”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C语言如何实现杨氏矩阵”吧!题目如下:有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编
2023-07-05

C语言如何实现矩阵连乘

本篇内容主要讲解“C语言如何实现矩阵连乘”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C语言如何实现矩阵连乘”吧!动态规划法题目描述:给定n个矩阵{A1,A2....An},其中Ai与Ai+1是
2023-06-16

C++如何实现验证二叉搜索树

本文小编为大家详细介绍“C++如何实现验证二叉搜索树”,内容详细,步骤清晰,细节处理妥当,希望这篇“C++如何实现验证二叉搜索树”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。验证二叉搜索树Example 1:In
2023-06-19

web用php如何实现搜索功能

本篇内容介绍了“web用php如何实现搜索功能”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!创建搜索表单在网站主页面上添加一个搜索表单,通常
2023-07-05

PHP如何实现模糊搜索功能

在PHP中实现模糊搜索功能是一项常见的需求,特别是在开发网站或应用程序中涉及到搜索功能时。模糊搜索可以帮助用户更快速准确地找到他们需要的信息。下面将介绍如何在PHP中实现模糊搜索功能,并提供具体的代码示例。1. 数据库准备首先,我们需要
PHP如何实现模糊搜索功能
2024-03-06

css如何实现带搜索图标的搜索框功能

这篇文章给大家分享的是有关css如何实现带搜索图标的搜索框功能的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。前言给大家分享一下前端用处很多的带小图标的搜索框的制作方法。效果展示基本思路1、搜索图像用绝对定位放到搜
2023-06-08

如何使用 PHP 实现搜索功能

通过以下步骤实现 php 搜索功能:建立数据库连接定义搜索查询(使用 like 运算符)执行查询并获取结果显示搜索结果(按用户输入的搜索词筛选)如何使用 PHP 实现搜索功能搜索功能是网站中必不可少的组件,它允许用户轻松地查找所需信息。本
如何使用 PHP 实现搜索功能
2024-05-02

Vue如何实现简单搜索功能

这篇文章主要讲解了“Vue如何实现简单搜索功能”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Vue如何实现简单搜索功能”吧!1、概述在vue项目中,搜索功能是我们经常需要使用的一个场景,最常
2023-07-05

C++如何实现转置矩阵的循环

这篇文章主要介绍了C++如何实现转置矩阵的循环,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。前言矩阵的转置主要考查我们对循环的使用,通过简单的循环结构,我们可以很方便的完成矩
2023-06-22

Flutter如何实现扫二维码功能

这篇文章主要为大家展示了“Flutter如何实现扫二维码功能”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“Flutter如何实现扫二维码功能”这篇文章吧。具体内容如下首先在pubspec.yam
2023-06-29

Ajax如何实现智能提示搜索功能

这篇文章主要介绍Ajax如何实现智能提示搜索功能,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!一、效果图:二、实现过程: 思路: 三、部分代码:html:

php如何实现关键字搜索功能

这篇文章主要介绍“php如何实现关键字搜索功能”,在日常操作中,相信很多人在php如何实现关键字搜索功能问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”php如何实现关键字搜索功能”的疑惑有所帮助!接下来,请跟
2023-06-26

Redis如何实现分布式搜索功能

Redis是一款高性能的NoSQL数据库,其提供了丰富的功能和数据结构,包括字符串、哈希表、列表、集合和有序集合等。除此之外,Redis还提供了一些高级功能,例如发布订阅、Lua脚本和事务等。其中,Redis的分布式搜索功能非常实用,可以帮
Redis如何实现分布式搜索功能
2023-11-08

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录