矩阵元素查找

[编程题]矩阵元素查找

热度指数：29706 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

已知一个有序矩阵mat，同时给定矩阵的大小n和m以及需要查找的元素x，且矩阵的行和列都是从小到大有序的。设计查找算法返回所查找元素的二元数组，代表该元素的行号和列号(均从零开始)。保证元素互异。

数据范围： $0 \le n,m \le 1000$ ，矩阵中的任何元素满足 $0 < mat_{i,j} \le 1000000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n+m)$

示例1

输入

[[1,2,3],[4,5,6]],2,3,6

输出

[1,2]

示例2

输入

[[1,2,3]],1,3,2

输出

[0,1]

算法知识视频讲解

棒棒糖🍭201906101800876

发表于 2021-07-16 10:39:28

精华题解 nc86.矩阵元素查找 1. 思路一: (笨办法, 暴力搜索, 不合要求) 直接遍历二维数组即可. class Solution { public: vector<int> findElement(vector<vector<int> > mat, int 展开全文

不会做题的小菜鸡

发表于 2021-07-17 15:16:41

精华题解思路暴力搜索，双重循环遍历依据有序性按照一定顺序来查找方法一：暴力搜索双重循环直接遍历所有元素找到指定元素 class Solution { public: vector<int> findElement(vector<vector<int> > 展开全文

LaN666

发表于 2020-12-06 19:29:12

思路分析：从矩阵的左下角开始，因为每行每列都是有序的。 import java.util.*; public class Finder { public int[] findElement(int[][] mat, int n, int m, int x) { int nn 展开全文

badly1226

发表于 2021-11-23 14:50:07

// write code here int[] result = new int[2]; int row = 0; int col = m - 1; while(row < n && col >= 0) { 展开全文

执子一白

发表于 2020-12-08 12:06:37

二分查找或者顺序查找都可以，这个题有点恶心，他说行和列都是从小到大有序的结果只是行内有序，还以为整个在列上也是递增呢，恶心……所以查找符合条件行时没办法使用二分，这里老老实实循环，找行中匹配元素时可以使用二分 import java.util.*; public class Finder { 展开全文

摸鱼学大师

发表于 2021-07-16 16:58:58

思路：题目中给的信息：行和列都是有序的，且元素互异寻找的是目标值的坐标，从零开始即这是一个二维矩阵上的查找，查找算法如下：方法一：暴力搜索直接两个for循环找到目标值的坐标 class Solution { public: vector<int> findElem 展开全文

OfferCall！

发表于 2021-04-05 16:21:35

由于给定的二维数组具备每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。我们可以从矩阵的右上角元素开始进行查询，如果其等于目标元素则直接返回结果；如果其大于目标元素，则只能往列坐标减少的方向去寻找，其他位置的元素都是大于当前访问的元素的，自然也就大于目标元素；展开全文