74. Search a 2D Matrix
74. Search a 2D Matrix
题目
You are given an m x n
integer matrix matrix
with the following two properties:
- Each row is sorted in non-decreasing order.
- The first integer of each row is greater than the last integer of the previous row.
Given an integer target
, return true
if target
is in matrix
orfalse
otherwise.
You must write a solution in O(log(m * n))
time complexity.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4
题目大意
给你一个满足下述两条属性的 m x n
整数矩阵:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target
,如果 target
在矩阵中,返回 true
;否则,返回 false
。
解题思路
这道题说 matrix
从上到下递增,从左到右递增,显然左上角是最小元素,右下角是最大元素。我们如果想高效在 matrix
中搜索一个元素,肯定需要从某个角开始,比如说从左上角开始,然后每次只能向右或向下移动,不要走回头路。
如果真从左上角开始的话,就会发现无论向右还是向下走,元素大小都会增加,那么到底向右还是向下?不确定,那只好用类似 动态规划算法 的思路穷举了。
但实际上不用这么麻烦,我们不要从左上角开始,而是从右上角开始,规定只能向左或向下移动。
你注意,如果向左移动,元素在减小,如果向下移动,元素在增大,这样的话我们就可以根据当前位置的元素和 target
的相对大小来判断应该往哪移动,不断接近从而找到 target
的位置。
代码
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function (matrix, target) {
const h = matrix.length;
const w = matrix[0].length;
let i = 0;
let j = w - 1;
while (i < h && j >= 0) {
if (matrix[i][j] == target) return true;
if (matrix[i][j] < target) {
i++;
} else {
j--;
}
}
return false;
};
相关题目
- [240. 搜索二维矩阵 II](./0240.md)
- [2468. 根据限制分割消息](https://leetcode.cn/problems/split-message-based-on-limit)