首页 > 试题广场 >

矩阵查数

[编程题]矩阵查数
  • 热度指数：5561 时间限制：C/C++ 4秒，其他语言8秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给定一个二维整型矩阵，已知矩阵的每一行都按照从小到大的顺序排列，每一列也都按照从小到大的顺序排列。现在给出一个数，请写一个函数返回该数是否存在于矩阵中。
矩阵中出现的数字与需要查找的数(k)都为0~100000之间的整数，且矩阵的大小在3000*3000以内。
在保证正确性的基础上，请尽量给出比较高效的解法。请列出你的算法时间复杂度与空间复杂度分别是多少？


输入描述:
输入两个整数m,n, 且 0<m<=3000, 0<n<=3000。

接着输入一个vector<vector<int>> matrix矩阵，大小为m行n列，与一个int k，为需要查找的数字。


输出描述:
输出true或者false，true表示该数k存在于该matrix矩阵中，false表示该数k不存在于该matrix矩阵中。
示例1

输入

3 3
​​2 3 5
​​3 4 7
​​3 5 8
4

输出

true

说明

4位于矩阵的第二行第二列，故输出true
算法知识视频讲解
开通博客
头像 bao_hu_yuan_zhang
发表于 2024-03-03 19:52:40
#include <iostream> #include <unordered_map> using namespace std; int main() { int m=0; int n=0; cin>>m; cin>&g 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客题解官
发表于 2020-06-05 16:34:31
题解 题目难度：简单知识点：数学逻辑、数组 方法一： 思路：1：将数据输入动态数组matrix中，从左下脚开始遍历，初始行数i=m-1,初始列数j=0。 2：判断现在所在行数i，j=0，即matrix[i][0]与K值进行比较，如果matrix[i][0]>k,由于每行元素值依次增大，所以一定 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

数组 算法工程师 第四范式 2019 查找
上传者：小小
难度：
33条回答 7299浏览

热门推荐

通过挑战的用户

查看代码

相关试题

矩阵查数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号