题解 | #矩阵元素查找#

思路

• 暴力搜索，双重循环遍历
• 依据有序性按照一定顺序来查找

方法一：暴力搜索

双重循环直接遍历所有元素找到指定元素

class Solution {
public:
    vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {
        // write code here
        for(int i = 0; i < n; i++) {                // 遍历行
            for(int j = 0; j < m; j++) {            // 遍历列
                if(mat[i][j] == x) return {i,j};    // 如果找到相等的元素则返回坐标
            }
        }
        return {};
    }
};

复杂度分析

• 时间复杂度：O(n^2)，双重循环的时间
• 空间复杂度：O(1)，未引入任何其他空间消耗

方法二：按序搜索（二分的思路）

由于二维数组是有序的，我们只需要选择起点为左下角处，从这里出发，向右的数字都比当前大，向上的数字都比当前小，因此实现了一个单右方向和单上方向的寻找路线，大大节省了时间代价

class Solution {
public:
    vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {
        // write code here
        for(int i = n-1, j = 0; i>=0 && j < m;) {        // 构造起点
            if(mat[i][j] == x) return {i,j};             // 如果找到目标值则返回坐标
            if(mat[i][j] > x) i--;                       // 如果当前值大于目标值则向上单向寻找
            if(mat[i][j] < x) j++;                       // 如果当前值小于目标值则向右单向寻找
        }
        return {};
    }
};

复杂度分析

• 时间复杂度：O(M+N)，最长的查找时间也是扫过一长一宽的时间
• 空间复杂度：O(1)，不需要无额外空间申请