题解 | #矩阵元素查找#

算法思想一：暴力循环法

解题思路：

主要是对矩阵元素进行全部遍历查找目标值，采用双层遍历的方式

代码展示：

Python版本

class Solution:
    def findElement(self, mat, n, m, x):
        # write code here
        res = []
        # 特殊情况
        if n == 0:
            return res
        # 两层遍历暴力搜索
        for i in range(n):
            for j in range(m):
                # 搜索目标值，将坐标位置信息存入返回数组中
                if mat[i][j] == x:
                    res.append(i)
                    res.append(j)
        return res

复杂度分析

时间复杂度 $O(nm)$ ：n,m表示矩阵的行列数量，双层遍历时间 $O(nm)$

空间复杂度 $O(1)$ ：仅使用常数级变量空间，存储目标值索引数组

算法思想二：二分法

解题思路：

由题可知：行和列都是有序的，且元素互异，左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反

因此可以采用二分法：

首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。
图解：

代码展示：

import java.util.*;
public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        // 初始化
        int[] res = new int[2];
        int i = n-1;
        int j = 0;
        // 循环结束条件
        while (i >= 0 && j < m){
            // 找到目标值返回目标的坐标
            if (mat[i][j] == x){
                res[0] = i;
                res[1] = j;
                return res;
            // mat[i][j] > x 则将搜索位置向上移动一位
            }else if(mat[i][j] > x){
                i--;
            }else{
                // mat[i][j] < x 则将搜索位置向右移动一位
                j++;
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度 $O(n+m)$ ：n,m表示矩阵的行列数量，最多走过矩阵的两个边长

空间复杂度 $O(1)$ ：仅使用常数级变量空间