数据结构学习 jz04二维矩阵找数字

题目：

解法一：找角落点，然后渐进目标（像二叉搜索树）

时间复杂度O(n+m)

空间复杂度O(1)

#include <vector>
#include <iostream>
//解法一 找到角落的一个点，然后渐进目标
class Solution {
public:
    bool findTargetIn2DPlants(std::vector<std::vector<int>>& plants, int target) {

        if (plants.size() == 0 || plants[0].size() == 0) return false;//防止是空的
        int m = plants[0].size();
        int n = plants.size();
        for (int x = 0, y = n-1; y >= 0 && x < m;)//从左下角向中心找目标点，要是找出界还没找到就返回false
        {
            if (plants[y][x] == target)//找到啦
                return true;
            else if (plants[y][x] > target)
                y--;
            else
                x++;
        }
        return false;

    }
};

void Test_solution1()
{
    //std::vector<std::vector<int>> x{ {2, 3, 6, 8},{4, 5, 8, 9},{5, 9, 10, 12} };
    std::vector<std::vector<int>> x{ {-5} };
    int target = -2;
    Solution solu;
    std::cout << solu.findTargetIn2DPlants(x, target) << std::endl;
}

解法二：二分查找

在对角线上迭代，对于每一个对角线元素，对该元素所在的行和列使用二分搜索

时间复杂度O(logk!) k=max{m,n}

空间复杂度O(1)

#include <iostream>
#include <vector>
//二分查找
//故意不写成递归是希望多锻炼一下直接写成循环的能力
class Solution {
public:
    bool findTargetIn2DPlants(std::vector<std::vector<int>>& plants, int target) {
        if (plants.empty() || plants[0].empty()) return false;
        int m = plants[0].size()-1;
        int n = plants.size()-1;
        int row = 0;
        int column = 0;
        while (row <= n && column <= m)//在对角线上迭代，对于每一个对角线元素，对该元素所在的行和列使用二分搜索
        {
            //在行上使用二分查找
            int up = row;
            int down = n;
            while (up <= down)
            {
                int mid_row = (up + down) / 2;
                if (plants[mid_row][column] > target)
                {
                    down = mid_row - 1;
                }
                else if (plants[mid_row][column] < target)
                {
                    up = mid_row + 1;
                }
                else
                {
                    return true;
                }
            }
            //在列上使用二分查找
            int left = column;
            int right = m;
            while (left <= right)
            {
                int mid_column = (left + right) / 2;
                if (plants[row][mid_column] > target)
                {
                    right = mid_column - 1;
                }
                else if (plants[row][mid_column] < target)
                {
                    left = mid_column + 1;
                }
                else
                {
                    return true;
                }
            }
            ++row;
            ++column;
        }
        return false;
    }
};

解法三：递归，在列上二分查找，在行上遍历

递归。

在列上用二分法，在行上遍历所有。

1. 先在mid列上找到plants[row][mid] < target =< lants[row+1][mid]的行row
2. 然后排除找到的行列的交点的左上（一定比目标小）和右下（一定比目标大）
3. 接着分成右上和左下，分别调用函数进行递归

时间复杂度O(nlogm)

空间复杂度O(1)

#include <iostream>
#include <vector>
//解法三，递归 在列上用二分法，在行上遍历所有 先在mid列上找到plants[row][mid] < target =< lants[row+1][mid]的行row
//然后排除找到的行列的交点的左上（一定比目标小）和右下（一定比目标大）
//接着分成右上和左下，分别调用函数进行递归
class Solution {
public:
    bool findTargetIn2DPlants(std::vector<std::vector<int>>& plants, int target) {
        if (plants.size() == 0 || plants[0].size() == 0) return false;
        int right = plants[0].size() - 1;
        int down = plants.size() - 1;
        return search_target(plants, target, 0, down, 0, right);
    }
    bool search_target(std::vector<std::vector<int>>& plants, int target, int up, int down, int left, int right)
    {
        if (left > right || up > down) return false;//找不到，超出范围
        
        int mid = (left + right) / 2;//二分 列
        int row = 0;
        while (plants[row][mid] < target && row < down) ++row;//找行
        if (plants[row][mid] == target) return true;//找到了
        //递归
        //后一个row不能是row+1，不然过不了{ {1,3,5} }
        //两边只要有一边找到即可
        return search_target(plants, target, up, row, mid + 1, right) || search_target(plants, target, row, down, left, mid - 1);
    }
};
void Test_solution3()
{
    //std::vector<std::vector<int>> x{ {2, 3, 6, 8},{4, 5, 8, 9},{5, 9, 10, 12} };
    std::vector<std::vector<int>> x{ {1,3,5} };
    int target = 1;
    Solution solu;
    std::cout << solu.findTargetIn2DPlants(x, target) << std::endl;
}

运行结果

二分查找非常快哦。。。。