☆打卡算法☆LeetCode 74、搜索二维矩阵 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个矩阵，判断矩阵中是否有目标值。”

题目链接：

来源：力扣（LeetCode）

链接：74. 搜索二维矩阵 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例 1：
输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出： true

示例 2：
输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出： false

二、解题

1、思路分析

根据题意可以判断，居集镇的第一列的元素时升序的。

对矩阵的第一列元素可以二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。

2、代码实现

代码参考：

public class Solution {
        public bool SearchMatrix(int[][] matrix, int target)
        {
            //先列再行二分查找
            int m = matrix.Length;
            //int n = matrix[0].Length;
            int[] firstCol = new int[m];
            for (int i = 0; i < m; i++)
            {
                firstCol[i] = matrix[i][0];
            }
            (int colRes, int left) = binarySerarch(firstCol, target);
            if (colRes >= 0) return true;
            (int res, _) = binarySerarch(matrix[left], target);
            return res > -1;
        }

        private (int res, int left) binarySerarch(int[] arr, int target)
        {
            int left = 0;
            int right = arr.Length - 1;
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (arr[mid] == target) return (mid, left);
                if (arr[mid] > target) right = mid - 1;
                else left = mid + 1;
            }
            return (-1, left > 0 ? left - 1 : 0);
        }
}

3、时间复杂度

时间复杂度 ： O(log m + log n)

其中m和n分别是矩阵的行数和列数

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

遇到与目标数相等的数即返回true:

将target与每一行最后一个数比较，

如果小于该行最后一个数，向前比较，

遇到大于该数且前一列小于该数的说明没有可以匹配的数，返回false;

遍历完如果没有可以匹配的，返回false.