“给定一个矩阵,判断矩阵中是否有目标值。”
题目链接:
来源:力扣(LeetCode)
链接:74. 搜索二维矩阵 - 力扣(LeetCode) (leetcode-cn.com)
编写一个高效的算法来判断 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
根据题意可以判断,居集镇的第一列的元素时升序的。
对矩阵的第一列元素可以二分查找,找到最后一个不大于目标值的元素,然后在该元素所在行中二分查找目标值是否存在。
代码参考:
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);
}
}
时间复杂度 : O(log m + log n)
其中m和n分别是矩阵的行数和列数
空间复杂度: O(1)
只需要常数级别的空间存放变量。
遇到与目标数相等的数即返回true:
将target与每一行最后一个数比较,
如果小于该行最后一个数,向前比较,
遇到大于该数且前一列小于该数的说明没有可以匹配的数,返回false;
遍历完如果没有可以匹配的,返回false.