矩阵元素查找（二分）

题意

给一个二维数组,行列分别有序,在数组中找给定的值的位置

思路分析

考虑一维数组

如果数组是一维的,那么有序可以直接二分控制查找的左右坐标

对于二维数组考虑

考虑把一维的左右坐标,变成二维数组中一个矩形范围的4个坐标

不幸的是,一个子的二位数组,从数值上,并不满足是一段连续的从小到大的区间.

如样例数据一中的2,5从数值上3,4都在2,5之间

考虑角上的数据

注意到mat[0][m-1]这个角,很特殊的,它刚好是这行的最大值,同时又是这列的最小值.

换句话说,如果这个值大于要找的值,那么这一列的值都大于要找的值.

如果这个值小于要找的值,那么这一行的值都小于要找的值.

那么每次比较不相等时,总可以去掉一行或一列

找到结果

直到从二维数组降级为一维数组时,使用二分搜索去找值的坐标

题目样例

以题目样例为例

第一次把角落的3和6比较,比6小所以删除第一行

删除后变成了一维数组,直接二分找6,输出坐标即可

题解

所以整合上面的内容

class Solution {
public:
    vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {
        int i0 = 0;
        int i1 = n-1;
        int j0 = 0;
        int j1 = m-1;
        while(i0 != i1 && j0 != j1){ // 每次处理角落
            if(mat[i0][j1] == x)return {i0,j1}; // 相等直接返回
            if(mat[i0][j1] > x)j1--; // 移除列
            else i0++; // 移除行
        }
        if(i0 == i1){ // 一行
            return {
                i0,
                int(lower_bound(mat[i0].begin(), mat[i0].end(),x) - mat[i0].begin()) // 二分找下标
           };
        }else{ // 一列
            vector<int> arr; // 提取列元素
            for(int i = 0;i < n;i++)arr.emplace_back(mat[i][j0]);
            return {
                int(lower_bound(arr.begin(),arr.end(),x)-arr.begin()), // 二分找下标
                j0
            };
        }
        // 不会到达
        assert(false);
        return {-1,-1};
    }
};

复杂度分析

空间复杂度: 只用了常数个额外变量,所以空间复杂度为$O(1)O(1)$

时间复杂度: 每次让横纵坐标简一, 最后有一个二分一维数组,所以时间复杂度为$O(max(log(max(n,m)),n+m))O(max(log(max(n,m)),n+m))$