描述

题目描述

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

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

示例

输入：
[[1,2,3],[4,5,6]],2,3,6
返回值：
[1,2]

知识点：二分查找、分治算法

难度：⭐⭐⭐

题解

图解

方法一：分治法（右上角）

解题思路：

从题目给出的要求时间复杂度至少为 O(n+m) 也可以猜出，最坏的情况会遍历一行加一列的长度

算法流程：

• 分治, 右上角开始查找
• 从右上角开始比较，等于x则直接返回，小于x则往下查找；大于x，则往左查找

Java 版本代码如下：

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        int i = 0, j = m - 1;
        // 分治, 右上角开始二分查找
        while(i < n && j >= 0) {
            if(mat[i][j] == x) {
                break;
            } else if(mat[i][j] < x) {
                // 小于x，则往下查找
                i++;
            } else {
                // 大于x，则往左查找
                j--;
            }
        }
        return mat[i][j] == x ? new int[]{i, j} : new int[]{-1, -1};

    }
}

复杂度分析：

时间复杂度 $O(n+m)O(n+m)$：n为行数，m为列数，平均遍历长度是从右上角遍历到左下角，最坏的情况是x在左下角元素

空间复杂度 $O(1)O(1)$：计算过程只用到常数个变量

方法二：分治法（左下角）

解题思路：

相对于从右上角开始查找，相应的，我们也可以从左下角进行查找

算法流程：

• 分治, 左下角开始查找
• 从左下角开始查找，等于x则直接返回，小于x则往右边查找；大于x，则往上查找

Java 版本代码如下：

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        int i = n - 1, j = 0;
        // 分治, 左下角开始二分查找
        while(i >= 0 && j < m) {
            if(mat[i][j] == x) {
                break;
            } else if(mat[i][j] < x) {
                // 小于x，则往右查找
                j++;
            } else {
                // 大于x，则往上查找
                i--;
            }
        }
        return mat[i][j] == x ? new int[]{i, j} : new int[]{-1, -1};

    }
}

复杂度分析：

时间复杂度 $O(N+M)O(N+M)$：n为行数，m为列数，平均遍历长度是从左下角遍历到右上角，最坏的情况是x在右上角元素

空间复杂度 $O(1)O(1)$：计算过程只用到常数个变量