剑指 Offer 04 二维数组中的查找

概述

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

https://leetcode.com/problems/search-a-2d-matrix-ii/

暴力遍历法

直接遍历整个数组来找目标值。

时间复杂度 O(n*m)。

遍历前可以先用用矩阵四周的值缩减查找范围。

二分查找法

简单粗暴的话就是每行或每列都做二分查找。

时间复杂度 O(nlogm)

排序法

直接把二维数组排序成一维向量，之后再二分查找。 时间复杂度 O(n*mlog(m))

动态规划法

时间复杂度 O(n*m)。

class Solution {
public:
    vector<vector<int>> matrix;
    vector<vector<bool>> accessed;
    int target;
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        if (n == 0) return false;
        int m = matrix[0].size();
        if (m == 0) return false;
        this->matrix = matrix;
        this->target = target;
        vector<vector<bool>> accessed(n, vector<bool>(m, false));
        this->accessed = accessed;
        return dp(n-1, m-1);
    }

    bool dp(int x, int y) {
        if (x < 0 || y < 0) return false;
        if (accessed[x][y]) return false;
        if (matrix[x][y] == target) return true;
        if (matrix[x][y] < target) {
            accessed[x][y] = true;
            return false;
        }
        auto result = dp(x-1, y) || dp(x, y-1);
        if (result) {
            return true;
        } else {
            accessed[x][y] = true;
            return false;
        }
    }
};

Links: sword-offer-04

未经允许，禁止转载，本文源站链接：https://iamazing.cn/