一、题目
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.
